PHP中最長的公共子串演算法實作原理-php教程-PHP中文網

PHP中最長的公共子串演算法實作原理

WBOY

發布： 2023-07-07 13:56:02

原創

1145 人瀏覽過

PHP中的最長公共子字串演算法實作原理

最長公共子字串（Longest Common Substring）是一種常用的字串比對演算法，用於尋找兩個字串中最長的相同連續子字串。在PHP中，我們可以透過動態規劃演算法來實現最長公共子字串的查找。

下面我們將詳細介紹PHP中最長公共子字串演算法的實作原理，並附上相關的程式碼範例。

動態規劃演算法原理

動態規劃演算法用於解決具有重疊子問題並具有最優子結構性質的問題。最長公共子字串問題滿足這些條件，因此可以使用動態規劃演算法來解決。

最長公共子字串的問題可以形式化為：給定兩個字串S1和S2，求它們的最長公共子字串LCS。

動態規劃演算法的核心思想是，將問題分為若干個子問題，並透過求解子問題的最優解來求得原問題的最優解。對於最長公共子字串問題，我們可以將其分為更小的子問題。對於字串S1的前i個字符和字串S2的前j個字符，我們可以判斷S1[i]和S2[j]是否相等，如果相等，則可以得到一個新的子問題，即求解S1的前i-1個字元和S2的前j-1個字元的最長公共子字串。如果不相等，則最長公共子串的長度為0。

透過上述的分割過程，我們可以建立一個二維的表格進行動態規劃求解。表格的行表示S1的字符，列表示S2的字符，每個單元格表示S1前i個字符和S2前j個字符的最長公共子串的長度。最終，表格右下角的單元格即為所求的最長公共子字串的長度。

最長公共子字串演算法實作

下面我們給出PHP中最長公共子字串演算法的程式碼實作：

function longestCommonSubstring($str1, $str2) {
    $length1 = strlen($str1);
    $length2 = strlen($str2);

    // 初始化二维数组
    $dp = array();
    for ($i = 0; $i <= $length1; $i++) {
        $dp[$i] = array();
        for ($j = 0; $j <= $length2; $j++) {
            $dp[$i][$j] = 0;
        }
    }

    $maxLen = 0;
    $endIndex = 0;

    // 动态规划求解
    for ($i = 1; $i <= $length1; $i++) {
        for ($j = 1; $j <= $length2; $j++) {
            if ($str1[$i - 1] == $str2[$j - 1]) {
                $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
                if ($dp[$i][$j] > $maxLen) {
                    $maxLen = $dp[$i][$j];
                    $endIndex = $i - 1;
                }
            }
        }
    }

    // 根据最长公共子串的长度和结束索引截取子串
    $longestSubstring = substr($str1, $endIndex - $maxLen + 1, $maxLen);

    return $longestSubstring;
}

// 示例
$str1 = "ABCABC";
$str2 = "BABCAB";

$result = longestCommonSubstring($str1, $str2);
echo "最长公共子串：".$result;

登入後複製

在上述在程式碼中，我們先計算字串S1和S2的長度，並初始化一個二維陣列$dp用於儲存動態規劃的結果。然後，透過雙重循環遍歷S1和S2，並根據當前字元是否相等來更新$dp數組的值。

最後，根據最長公共子字串的長度和結束索引，使用substr函數截取最長公共子字串並傳回。