在Python中确定构建给定字符串的最小成本的程序

假设我们需要构建长度为n的字符串’str’，我们可以执行两个操作来构建此字符串。

可以将一个字符添加到str的末端，成本为a。
可以将子字符串sub_str添加到str的末端，成本为r。

我们必须计算构建字符串str的最小成本。

因此，如果输入为a=5，r=4，str=’tpoint’，则输出将为29。

构建字符串’tpoint’的成本如下所述 −

str='t'; 添加一个新字符，因此成本为5。
str = 'tp'; 添加一个新字符，因此成本为5。
str = 'tpo'; 添加一个新字符，因此成本为5。
str = 'tpoi'; 添加一个新字符，因此成本为5。
str = 'tpoin'; 添加一个新字符，因此成本为5。
str = 'tpoint'; 添加子字符串't'，因此成本为4。

总成本为5+5+5+5+5+4=29。

为了解决这个问题，我们将遵循以下步骤 −

size:=str的大小
largest:=一个新列表
low:=0
对于upp在范围1到size + 1之间做以下操作，
- 当从下标low到upp的str未出现在str从下标0到low的位置时，执行以下操作
  - low:=low+1
- 将（upp-low）插入largest的末尾
c:=包含a的新列表
对于i在范围1到size之间进行以下操作，
- 如果largest[i]与0相同，则
  - 把（c的最后一个元素+a）插入到c的末尾
- 否则，
  - 在c的末尾插入（c的最后一个元素+a）和（c[i-largest[i]]+r）中的最小值
返回c的最后一个元素

示例

让我们看以下实现以更好地理解−

def solve(a, r, str):
   size = len(str)
   largest = []
   low = 0
   for upp in range(1, size+1):
      while str[low:upp] not in str[:low]:
         low += 1
      largest.append(upp - low)

   c = [a]
   for i in range(1, size):
      if largest[i] == 0:
         c.append(c[-1] + a)
      else:
         c.append(min(c[-1] + a, c[i - largest[i]] + r))

   return c[-1]

print(solve(5, 4, 'tpoint'))