最長共同子字串

最長共同子字串（Longest Common Substring）問題是計算兩個或更多字元串中共享的最長子字元串。例如，對於字元串 "ABCDEF" 和 "ADEF"，它們的最長共同子字元串是 "ADEF"。

這個問題可以用動態規劃（Dynamic Programming）來解決。我們可以定義一個二維數組 lcs[i][j]，其中 i 和 j 分別表示字元串 A 和 B 的下標，lcs[i][j] 表示字元串 A 的第 i 個字元和字元串 B 的第 j 個字元之間的最長共同子字元串的長度。

使用動態規劃的方法，我們可以通過以下遞推關係來計算 lcs[i][j]：

• 如果 A[i] != B[j]，那麼 lcs[i][j] = 0。
• 如果 A[i] == B[j]，那麼 lcs[i][j] = 1 + lcs[i-1][j-1]。

這裡的 A[i] 表示字元串 A 的第 i 個字元，B[j] 表示字元串 B 的第 j 個字元，lcs[i-1][j-1] 表示 A[0..i-1] 和 B[0..j-1] 的最長共同子字元串的長度。

最後，我們可以通過檢查 lcs[len(A)][len(B)] 來找到字元串 A 和 B 的最長共同子字元串。

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

def lcs(str1, str2):
    m, n = len(str1), len(str2)
    lcs_length = [0] * (m + 1)
    for i in range(n):
        for j in range(m):
            if str1[j] == str2[i]:
                lcs_length[j + 1] = lcs_length[j] + 1
            else:
                lcs_length[j + 1] = 0
        m, n = m - 1, n - 1
        lcs_length[m + 1], m, n = lcs_length[m], n - 1, m
    return lcs_length[m]

# 示例
str1 = "ABCDGH"
str2 = "AEDFHR"
print(lcs(str1, str2))  # 輸出: 3

這個算法的時間複雜度為 O(mn)，其中 m 和 n 分別是字元串 A 和 B 的長度。空間複雜度為 O(m)，因為我們使用了 m 個單元的額外空間來存儲 lcs_length 數組。