Lcs算法求最長公共子串

LCS（Longest Common Subsequence）算法用於找到兩個或多個序列中最長的公共子序列。一個序列的子序列是通過刪除某些元素（可以是不連續的）得到的新序列。例如，"ABCD"的子序列包括"ABCD"、"ABD"、"ACD"、"BCD"、"ABC"、"AB"、"AC"、"AD"、"BC"、"BD"、"CD"、"A"、"B"、"C"和"D"。

最長的公共子序列（LCS）是指在兩個或多個序列中都可以找到的、長度最長的子序列。

LCS算法有很多變體，以下是其中一種基本的動態規劃算法來找到兩個序列之間的LCS：

  1. 定義狀態：設dp[i][j]表示前i個元素的序列1和前j個元素的序列2的最長公共子序列的長度。

  2. 邊界條件：dp[0][0] = 0，dp[0][j] = 0，dp[i][0] = 0（其中i, j >= 0），因為空字元串是任何序列的公共子序列。

  3. 狀態轉移方程：dp[i][j] = max(dp[i-1][j], dp[i][j-1]) if s1[i] == s2[j] else max(dp[i-1][j], dp[i][j-1]) + 1。

  4. 計算dp數組：從i=0和j=0開始，遞增i和j，並計算dp數組。

  5. 返回最大值：返回dp[len1][len2]，其中len1和len2是序列1和序列2的長度。

以下是一個簡單的Python實現：

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m):
        for j in range(n):
            if s1[i] == s2[j]:
                dp[i + 1][j + 1] = dp[i][j] + 1
            else:
                dp[i + 1][j + 1] = max(dp[i][j], dp[i + 1][j], dp[i][j + 1])

    return dp[m][n]

# 示例
s1 = "ABCDGH"
s2 = "AEDFHR"
print(lcs(s1, s2))

這個算法的時間複雜度和空間複雜度都是O(mn)，其中m和n是兩個序列的長度。對於大規模的序列，可能會有更高效的算法，比如使用二分查找或者分而治之的方法。