Python求最長公共子串

在字符串處理中，最長公共子串是一道非常常見的問題，涉及到了字符串處理的基本技巧。本文將以Python為例，詳細介紹如何使用動態規劃的思想，求解最長公共子串問題。

一、動態規劃求最長公共子串

動態規劃是一種常見的解決最優化問題的算法。對於最長公共子串問題，可以使用動態規劃求解。

具體來說，我們可以建立一個二維數組dp來記錄最長公共子串的長度。其中，dp[i][j]表示以第一個字符串的第i個字符為結尾，以第二個字符串的第j個字符為結尾的最長公共子串的長度。則二維數組中的最大值即為所求最長公共子串的長度。

在求解過程中，當兩個字符相同時，dp[i][j] = dp[i-1][j-1] + 1；否則dp[i][j] = 0。這個公式的含義是，如果前面已經匹配了一部分，當前匹配的字符相同，那麼在這基礎上加上當前匹配的字符所組成的字符串就是一個更長的公共子串。否則，當前的公共子串將被中斷。

二、Python代碼實現

def longest_common_substring(s1, s2):
    len1 = len(s1)
    len2 = len(s2)
    dp = [[0] * (len2+1) for _ in range(len1+1)]
    max_length = 0
    max_index = [0, 0]

    for i in range(1, len(dp)):
        for j in range(1, len(dp[i])):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > max_length:
                    max_length = dp[i][j]
                    max_index = [i, j]

    return s1[max_index[0]-max_length:max_index[0]], max_length

在上面的代碼中，我們首先創建了一個二維數組dp來存儲每個位置的最長公共子串的長度。這是一個動態規劃求解最長公共子串的必備數據結構。

然後，我們使用兩個嵌套的for循環遍歷兩個字符串s1和s2，在每個位置上計算其最長公共子串長度。如果兩個字符相等，則更新dp數組中當前位置的值為左上角位置的值加1（dp[i-1][j-1]+1）；否則當前位置的最長公共子串長度為0。

最後，我們在遍歷過程中更新最長公共子串的長度，以及最長公共子串的開始索引。最後，我們返回最長公共子串的具體字符串，以及對應的長度。

三、示例

下面是一個使用Python求解最長公共子串的示例，可以使用該示例代碼進行測試。

s1 = "abcde"
s2 = "cefgh"
longest_common_substring(s1, s2)
# Output: ("c", 1)

在上面的示例中，輸入字符串s1和s2的最長公共子串為”c”，長度為1。相信通過代碼的實現，讀者對於最長公共子串問題有了一定的理解和掌握。在實際開發過程中，掌握這種字符串匹配算法是非常有幫助的。