Python에서 세 문자열의 가장 긴 공통 부분 시퀀스의 길이를 찾는 프로그램

<시간/>

세 개의 문자열 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])의 최대값
dp[m, n, o]를 반환

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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"