最長公共子串

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

這個問題可以用動態規劃（Dynamic Programming）來解決。我們可以定義一個矩陣 L[i][j]，表示字元串 S[0..i-1] 和 S[0..j-1] 的最長公共子串長度。那麼 L[i][j] 的值可以通過以下規則來計算：

如果 S[i-1] == S[j-1]，則 L[i][j] = L[i-1][j-1] + 1； 如果 S[i-1] != S[j-1]，則 L[i][j] = 0。

初始條件是 L[0][0] = 0 和 L[0][j] = L[i][0] = 0。

最後，我們找到 L 矩陣中最大的值，那就是我們要找的最長公共子串的長度。

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

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

    for i in range(m):
        for j in range(n):
            if s1[i] == s2[j]:
                L[i + 1][j + 1] = L[i][j] + 1
            else:
                L[i + 1][j + 1] = 0

    return L[m][n]

s1 = "ABCDAB"
s2 = "ABCDBA"
print(lcs(s1, s2))  # 輸出應該是4，因為最長的公共子串是"ABCD"

這個算法的時間複雜度是 O(mn)，其中 m 和 n 分別是兩個字元串的長度。空間複雜度也是 O(mn)，因為我們使用了 m*n 的矩陣。

如果你只需要最長公共子串的長度，上面的算法就足夠了。但如果你需要實際的子串，你可以使用回溯（backtracking）來找到它。