Pythonで3つの文字列の最長共通部分列の長さを見つけるプログラム

3つの文字列s1、s2、およびs3があるとすると、それらの最長共通部分列の長さを見つける必要があります。

したがって、入力がs1 ="ababchemxde" s2 ="pyakcimde" s3 ="oauctime"の場合、最長共通部分列は "acme"であるため、出力は4になります。

これを解決するには、次の手順に従います-

• m：=s1のサイズ、n：=s2のサイズ、o：=s3のサイズ
• dp：=サイズ（o + 1）x（n + 1）x（m + 1）の3D行列
• 1からmの範囲のiについては、
  • 1からnの範囲のjについては、
    • 1からoの範囲のkについては、
      • 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] =（dp [i-1、j、k]、dp [i、j-1、k]およびdp [i、j、k-1]）の最大値
• return dp [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