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

長さ n の文字列「str」を構築することを考えてみましょう。この文字列を構築するには、次の2種類の操作を使用できます。

• コスト a で、str の末尾に1文字追加する。
• コスト r で、str の末尾に部分文字列 sub_str を追加する。

私たちの課題は、文字列 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 までの範囲でループする:
  • str のインデックス low から upp までの部分文字列が、インデックス 0 から low までの範囲内に存在しない間、次を繰り返す:
    • low := low + 1
  • largest の末尾に (upp − low) を挿入する
• c := a を含む新しいリストを作成
• i を 1 から size までの範囲でループする:
  • largest[i] が 0 と等しい場合:
    • c の末尾に (c の最後の要素 + a) を挿入する
  • それ以外の場合:
    • c の末尾に min(c の最後の要素 + a, c[i − largest[i]] + r) を挿入する
• c の最後の要素を返す

考え方のポイント

このアルゴリズムは動的計画法(DP)を利用しています。リスト c の各要素 c[i] は「最初の i+1 文字を構築するのに必要な最小コスト」を表します。各位置において、「新しい文字を1つ追加する(コスト a)」か「これまでに出現した部分文字列を末尾にコピーする(コスト r)」かの、より安い方を選択することで、文字列全体を構築する最小コストを効率よく求められます。

実装例

理解を深めるために、以下の実装を見てみましょう。

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