Pythonで3つ以上の文字列から最長の共通部分文字列を見つける方法【動的計画法】

最長共通部分文字列(Longest Common Substring)を求めるアルゴリズムは、動的計画法(DP)を用いることで効率的に解けます。一般的なDP実装では、O(nm)の時間計算量で処理が可能です(n、mは比較対象となる文字列の長さ)。以下に、最長共通部分文字列アルゴリズムの実装例を示します。

実装例

def longest_common_substring(s1, s2):
    m = [[0] * (1 + len(s2)) for i in range(1 + len(s1))]
    longest, x_longest = 0, 0
    for x in range(1, 1 + len(s1)):
        for y in range(1, 1 + len(s2)):
            if s1[x - 1] == s2[y - 1]:
                m[x][y] = m[x - 1][y - 1] + 1
                if m[x][y] > longest:
                    longest = m[x][y]
                    x_longest = x
            else:
                m[x][y] = 0
    return s1[x_longest - longest: x_longest]

print(longest_common_substring('wellbeing', 'welcome'))

このコードでは、「wellbeing」と「welcome」という2つの文字列を比較し、両方に共通して現れる最も長い部分文字列を抽出しています。

出力結果

wel

アルゴリズムの仕組み

このアルゴリズムは、以下の手順で動作します。

• まず、カウンターとして機能する2次元配列(m)を、すべて0で初期化します。

• 1行目から処理を開始し、文字列s1の各文字と、s2のすべての文字を順に比較していきます。

• s2の文字を走査している途中で、s1側の文字と一致した場合にはカウンターを1つ増やします。この値は、左上の対角位置の値を引き継ぐ形で、m[i][j]に保存されます。

すべてのループが終わった時点で、ループ内で記録しておいたインデックス情報をもとに、最も長かった部分文字列を切り出して返します。

Python 3で利用する際の注意点

オリジナルのコードで使用されていたxrange()はPython 2専用の関数です。Python 3環境では、組み込みのrange()に置き換えるだけで同じように動作します。上記のコードは、すでにPython 3向けに書き直したものです。

3つ以上の文字列へ拡張する方法

3つ以上の文字列から共通部分文字列を求めたい場合は、標準ライブラリのfunctools.reduce()を活用して、2文字列用の関数を繰り返し適用するのが手軽です。

from functools import reduce

strings = ['wellbeing', 'welcome', 'welfare']
result = reduce(longest_common_substring, strings)
print(result)

wel

この方法では、最初の2つの文字列の共通部分文字列を求め、その結果と次の文字列との共通部分文字列を求める……という処理を文字列の数だけ繰り返します。ただし、ペアごとの逐次処理であるため、厳密な意味で「全文字列に共通する最長の部分文字列」を必ず保証するわけではない点には注意してください。より厳密な結果が必要な場合は、一般化接尾辞木(generalized suffix tree)などを採用した手法の検討も有効です。