Pythonで2つの文字列の最長共通部分列の長さを求めるプログラム

2つの文字列 s1 と s2 が与えられたとき、両方の文字列にとって「特殊部分列」となる最長の文字列 s3 の長さを求めることを考えます。

ある文字列 x が別の文字列 y の特殊部分列であるとは、y から 0 個以上の文字を削除することで x が生成できることを意味します。これは、いわゆる「部分列(サブシーケンス)」と呼ばれる概念で、文字同士の順序関係さえ保たれていればよく、連続している必要はありません。

例として、s1 = 'pineapple'、s2 = 'people' が入力された場合を考えてみましょう。この場合の出力は 5 になります。長さ 5 の特殊部分列 'peple' が存在するためです。

この問題は、動的計画法(DP)を用いて効率的に解くことができます。以下の手順に従って進めます。

• prev := 存在しないキーに対して 0 を返す新しい辞書
• i を 0 から s1 の長さ - 1 まで繰り返す:
  • cur := 存在しないキーに対して 0 を返す新しい辞書
  • j を 0 から s2 の長さ - 1 まで繰り返す:
    • s1[i] と s2[j] が等しい場合、cur[j] := prev[j - 1] + 1、そうでない場合、cur[j] := max(cur[j - 1], prev[j])
  • prev := cur
• prev[s2 の長さ - 1] を返す

このアルゴリズムは、実質的に古典的な「最長共通部分列(LCS: Longest Common Subsequence)」問題の標準的な DP 解法です。時間計算量・空間計算量はともに O(len(s1) × len(s2)) となります。

実装例

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

from collections import defaultdict
def solve(s1, s2):
   prev = defaultdict(int)
   for i in range(len(s1)):
      cur = defaultdict(int)
      for j in range(len(s2)):
         cur[j] = prev[j - 1] + 1 if s1[i] == s2[j] else max(cur[j - 1], prev[j])
      prev = cur
   return prev[len(s2)-1]

s1 = 'pineapple'
s2 = 'people'
print(solve(s1, s2))

入力

'pineapple', 'people'

出力

5