Pythonで特定の文字列を構築するための最小コストを決定するプログラム

長さnの文字列'str'を作成する必要があるとします。文字列を作成するために、2つの操作を実行できます。

• コストaでstrの最後に文字を追加できます。
• コストrのstrの最後に部分文字列sub_strを追加できます。

文字列strを構築するための最小コストを計算する必要があります。

したがって、入力がa =5、r =4、str ='tpoint'のような場合、出力は29になります。

文字列'tpoint'を作成するためのコストは、以下のとおりです-

str = 't'; a new character added, therefore the cost is 5.
str = 'tp'; a new character added, therefore the cost is 5.
str = 'tpo'; a new character added, therefore the cost is 5.
str = 'tpoi'; a new character added, therefore the cost is 5.
str = 'tpoin'; a new character added, therefore the cost is 5.
str = 'tpoint'; substring 't' is added, therefore the cost is 4.

総費用は5+5 + 5 + 5 + 5 + 4=29です。

これを解決するには、次の手順に従います-

• size：=strのサイズ
• 最大：=新しいリスト
• 低：=0
• 範囲1からサイズ+1のuppの場合は、
  • str[インデックスlowからインデックスupp]がstr[インデックス0からインデックスlow]に存在しない場合、do
    • 低：=低+ 1
  • 最大の最後に挿入（upp-low）
• c：=を含む新しいリスト
• 1からサイズの範囲のiの場合は、
  • maximum [i]が0と同じ場合、
    • cの最後に（c + aの最後の要素）を挿入します
  • それ以外の場合、
    • cの最後に（c + aの最後の要素）、（c[i-最大[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'))

入力

5, 4, 'tpoint'

出力

29