Python動態規劃求解公共子串

本文將從以下多個方面對公共子串Python動態規划進行詳細闡述：

一、什麼是公共子串？

公共子串是指在兩個字元串中同時出現且連續的子串。例如，字元串”ABCD”和”BCDF”的公共子串是”BCD”。

二、如何使用動態規劃求解公共子串？

動態規劃是一種常用的求解最優化問題的演算法，在求解公共子串問題中也有廣泛的應用。對於兩個字元串，可以使用一個二維數組來表示它們的所有可能的子串。設置一個狀態數組dp，其中dp[i][j]表示以第一個字元串的第i個字元結尾和以第二個字元串的第j個字元結尾的最長公共子串的長度。狀態轉移方程如下：

if str1[i-1] == str2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = 0

其中，str1和str2是兩個字元串，i和j分別表示它們的下標。當兩個字元串的當前字元相同時，可以在當前字元串的最長公共子串基礎上加上一個字元，所以dp[i][j] = dp[i-1][j-1] + 1。當兩個字元串的當前字元不同時，它們的最長公共子串長度為0，即dp[i][j] = 0。

三、代碼示例

以下為使用動態規劃求解兩個字元串的最長公共子串的Python代碼示例：

def longest_common_substring(str1, str2):
    m = len(str1)
    n = len(str2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    max_len = 0
    end = 0
    for i in range(1, m+1):
        for j in range(1, n+1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
                if dp[i][j] > max_len:
                    max_len = dp[i][j]
                    end = i
            else:
                dp[i][j] = 0
    return str1[end-max_len:end]

在上述代碼中，首先定義了變數m和n分別表示兩個字元串的長度。接著，創建一個二維數組dp來存儲最長公共子串長度。使用max_len來最長公共子串的長度，end來記錄最長公共子串在第一個字元串中的結束字元的下標。最後，遍歷兩個字元串的所有可能子串並更新dp數組，在遍歷過程中更新max_len和end。最終，返回最長公共子串即可。

四、小結

本文詳細闡述了使用Python動態規劃求解公共子串的方法，其中重點介紹了狀態數組dp和狀態轉移方程，並提供了對應的Python代碼示例。對於讀者來說，可以通過本文學習動態規劃演算法的具體實現方法，並掌握如何在Python中實現最長公共子串的求解。