ボトムアップ方式の動的計画法で最長共通部分文字列を求めるPythonプログラム

ボトムアップアプローチによる動的計画法を用いて最長共通部分文字列（Longest Common Substring）を求める場合、まず小さな問題の解を計算するメソッドを定義します。一度計算した小さな問題の結果は、何度も再計算する必要はなく、必要になった時点で参照するだけで済みます。これにより、より大きな問題に対する解を効率的に組み立てることができます。

この手法の計算量はO(m×n)（mとnはそれぞれの文字列の長さ）であり、全探索よりも大幅に高速に動作する点が大きな特徴です。

サンプルコード

def compute_lcw(string_1, string_2):
    val = [[-1]*(len(string_2) + 1) for _ in range(len(string_1) + 1)]
    for i in range(len(string_1) + 1):
        val[i][len(string_2)] = 0
    for j in range(len(string_2)):
        val[len(string_1)][j] = 0
    lcw_i = lcw_j = -1
    lcw_len = 0
    for i in range(len(string_1) - 1, -1, -1):
        for j in range(len(string_2)):
            if string_1[i] != string_2[j]:
                val[i][j] = 0
            else:
                val[i][j] = 1 + val[i + 1][j + 1]
                if lcw_len < val[i][j]:
                    lcw_len = val[i][j]
                    lcw_i = i
                    lcw_j = j
    return lcw_len, lcw_i, lcw_j
string_1 = 'bull'
string_2 = 'bullied'
lcw_len, lcw_i, lcw_j = compute_lcw(string_1, string_2)
print("The longest common substring is : ")
if lcw_len > 0:
    print(string_1[lcw_i:lcw_i + lcw_len])

実行結果

The longest common substring is :
bull

コードの解説

• まず、compute_lcwという名前のメソッドを定義し、2つの文字列を引数として受け取ります。
• 2次元リストvalを作成し、各セルに「その位置から始まる共通部分文字列の長さ」を格納していきます。
• 文字列の末尾側から順に走査し、2つの文字列の対応する文字を比較して一致する部分があるかどうかを確認します。
• 文字が一致した場合は、斜め右下の値に1を加えた値を記録します。これにより、連続する一致文字列の長さが累積されていきます。
• 一致が見つかるたびに、現在の最大長を更新し、開始位置も別の変数に保存しておきます。
• この処理を文字列の終わりまで繰り返すことで、両方の文字列に共通する最長の部分文字列が特定されます。
• 最後に、2つの文字列を定義してメソッドを呼び出し、その結果（長さ・開始位置）を変数に代入します。
• 得られた開始位置と長さをもとに部分文字列を切り出し、コンソールに出力して表示します。

このようにボトムアップ型の動的計画法では、再帰呼び出しを行わずに表を順番に埋めていくため、スタックオーバーフローの心配がなく、大規模な文字列にも安定して対応できるのが利点です。