Chương trình tìm độ dài dãy con chung dài nhất của ba chuỗi trong Python

Cho ba chuỗi s1, s2, s3, tìm độ dài dãy con chung (Longest Common Subsequence - LCS) dài nhất của cả ba.

Ví dụ: s1="ababchemxde", s2="pyakcimde", s3="oauctime" → LCS là "acme" (độ dài 4).

Giải thuật (Quy hoạch động 3D)

• Khởi tạo mảng 3D dp kích thước (m+1) x (n+1) x (o+1) với 0.
• Duyệt i=1..m, j=1..n, k=1..o:
  • Nếu s1[i-1] == s2[j-1] == s3[k-1]: dp[i][j][k] = 1 + dp[i-1][j-1][k-1].
  • Ngược lại: dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1]).
• Kết quả: dp[m][n][o].

Mã nguồn Python

class Solution:
    def solve(self, s1, s2, s3):
        m, n, o = len(s1), len(s2), len(s3)
        dp = [[[0]*(o+1) for _ in range(n+1)] for _ 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))  # Output: 4

Đầu vào

"ababchemxde", "pyakcimde", "oauctime"

Đầu ra

4