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

問題概要

3つの文字列 s1、s2、s3 が与えられたとき、これらすべてに共通する最長共通部分列（LCS：Longest Common Subsequence）の長さを求めることを考えます。

たとえば、入力が以下のような場合を想定してみましょう。

• s1 = "ababchemxde"
• s2 = "pyakcimde"
• s3 = "oauctime"

この場合の出力は 4 になります。これは、3つの文字列すべてに共通する最長の部分列が "acme" であり、その長さが4文字だからです。

解き方（アルゴリズム）

この問題は動的計画法（DP）を用いて効率的に解くことができます。2つの文字列に対するLCSの考え方を、3次元のDPテーブルへと拡張します。具体的な手順は以下の通りです。

• m := s1 の長さ、n := s2 の長さ、o := s3 の長さ とします。
• (m + 1) × (n + 1) × (o + 1) のサイズを持つ3次元行列 dp を用意し、すべて 0 で初期化します。
• i を 1 から m まで繰り返します。
  • j を 1 から n まで繰り返します。
    • k を 1 から o まで繰り返します。
      • s1[i - 1]、s2[j - 1]、s3[k - 1] がすべて同じ文字である場合：
        dp[i][j][k] := 1 + dp[i - 1][j - 1][k - 1]
      • それ以外の場合：
        dp[i][j][k] := max(dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1])
• 最後に dp[m][n][o] を答えとして返します。

このアルゴリズムの時間計算量・空間計算量はいずれも O(m × n × o) となります。

Pythonでの実装例

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

class Solution:
   def solve(self, s1, s2, s3):
      m = len(s1)
      n = len(s2)
      o = len(s3)
      dp = [[[0 for i in range(o + 1)] for j in range(n + 1)] for k in range(m + 1)]
      for i in range(1, m + 1):
         for j in range(1, n + 1):
            for k in range(1, o + 1):
               if s1[i - 1] == s2[j - 1] == s3[k - 1]:
                  dp[i][j][k] = 1 + dp[i - 1][j - 1][k - 1]
               else:
                  dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k], dp[i][j][k - 1])
      return dp[m][n][o]
ob = Solution()
s1 = "ababchemxde"
s2 = "pyakcimde"
s3 = "oauctime"
print(ob.solve(s1, s2, s3))

入力

"ababchemxde", "pyakcimde", "oauctime"

出力

4