Implementation principle of longest common substring algorithm in PHP

The implementation principle of the longest common substring algorithm in PHP

The longest common substring (Longest Common Substring) is a commonly used string matching algorithm, used to find the longest of two strings of the same consecutive substring. In PHP, we can use dynamic programming algorithm to find the longest common substring.

Below we will introduce in detail the implementation principle of the longest common substring algorithm in PHP, and attach relevant code examples.

1. Principle of dynamic programming algorithm

The dynamic programming algorithm is used to solve problems with overlapping subproblems and optimal substructure properties. The longest common substring problem satisfies these conditions and can therefore be solved using a dynamic programming algorithm.

The problem of the longest common substring can be formalized as: given two strings S1 and S2, find their longest common substring LCS.

The core idea of ​​the dynamic programming algorithm is to divide the problem into several sub-problems and obtain the optimal solution to the original problem by solving the optimal solutions of the sub-problems. For the longest common substring problem, we can divide it into smaller sub-problems. For the first i characters of string S1 and the first j characters of string S2, we can determine whether S1[i] and S2[j] are equal. If they are equal, we can get a new sub-problem, that is, solve the problem of S1 The longest common substring of the first i-1 characters and the first j-1 characters of S2. If not equal, the length of the longest common substring is 0.

Through the above division process, we can construct a two-dimensional table for dynamic programming solution. The rows of the table represent the characters of S1, the columns represent the characters of S2, and each cell represents the length of the longest common substring of the first i characters of S1 and the first j characters of S2. Finally, the cell in the lower right corner of the table is the length of the longest common substring sought.

2. Implementation of the longest common substring algorithm

Below we give the code implementation of the longest common substring algorithm in 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;

In the above In the code, we first calculate the lengths of strings S1 and S2, and initialize a two-dimensional array $dp to store the results of dynamic programming. Then, iterate through S1 and S2 through a double loop and update the value of the $dp array based on whether the current characters are equal.

Finally, according to the length and end index of the longest common substring, use the substr function to intercept the longest common substring and return it.

3. Summary

The longest common substring algorithm is a commonly used string matching algorithm that is used to find the longest identical continuous substring in two strings. . In PHP, we can use dynamic programming algorithm to find the longest common substring. By constructing a two-dimensional table for dynamic programming solution, the longest common substring can be found efficiently.

Through the principles and code examples introduced in this article, I believe readers will have a deeper understanding of the implementation of the longest common substring algorithm in PHP. I hope this article will be helpful to readers when solving string matching problems.

The above is the detailed content of Implementation principle of longest common substring algorithm in PHP. For more information, please follow other related articles on the PHP Chinese website!