PHP实现求两个字符串最长公共子串的方法示例

问题描述

在字符串处理过程中，有时候需要找到两个字符串的最长公共子串。例如，在“abcdefg”和“bcdehijk”这两个字符串中，最长公共子串为“bcde”。在PHP中，我们可以用一些算法实现寻找最长公共子串。

算法实现

1.暴力枚举

暴力枚举是一种常见的寻找最长公共子串的方法，其时间复杂度为$O(mn^2)$，其中$m$和$n$分别为两个字符串的长度。其实现步骤如下：

1. 遍历第一个字符串的每一个字母。
2. 针对每一个第一个字符串的字母，遍历第二个字符串，并找到与它相同的字母。
3. 找到相同的字母之后，遍历两个字符串的下一个字母，直到找到不相同的字母为止。
4. 此时，记录下找到的串的长度和起始位置，继续执行步骤1、2、3，直到第一个字符串的所有字母都遍历完成。

下面是用PHP语言实现暴力枚举的代码示例：

function findLongestCommonSubstring(string $str1, string $str2): string
{
    $result = '';
    $length1 = strlen($str1);
    $length2 = strlen($str2);
    for ($i = 0; $i < $length1; $i++) {
        for ($j = 0; $j < $length2; $j++) {
            $k = 0;
            while (($i + $k < $length1) && ($j + $k < $length2) && ($str1[$i + $k] == $str2[$j + $k])) {
                $k++;
            }
            if ($k > strlen($result)) {
                $result = substr($str1, $i, $k);
            }
        }
    }
    return $result;
}

2. 动态规划

动态规划是一种常见的寻找最长公共子串的方法，其时间复杂度为$O(mn)$。其实现步骤如下：

1. 建立一个$m$行$n$列的二维数组$dp$，其中$dp[i][j]$表示以字符串1中第$i$个字符为结尾，以字符串2中第$j$个字符为结尾的最长公共子串的长度。
2. 遍历两个字符串，当发现两个字符串的一个字符相同时，令$dp[i][j] = dp[i-1][j-1] + 1$，否则$dp[i][j] = 0$。
3. 在$dp$数组中找到最大值，记录其位置和长度，即可找到最长公共子串。

下面是用PHP语言实现动态规划的代码示例：

function findLongestCommonSubstring(string $str1, string $str2): string
{
    $result = '';
    $length1 = strlen($str1);
    $length2 = strlen($str2);
    $dp = array_fill(0, $length1 + 1, array_fill(0, $length2 + 1, 0));
    $maxLen = 0;
    $maxColumn = 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];
                    $maxColumn = $j;
                }
            }
        }
    }
    if ($maxLen > 0) {
        $result = substr($str2, $maxColumn - $maxLen, $maxLen);
    }
    return $result;
}

示例说明

示例1

输入字符串1为“abcdefg”，字符串2为“bcdehijk”，输出字符串“bcde”。

使用暴力枚举的方法：

$str1 = 'abcdefg';
$str2 = 'bcdehijk';
$result = findLongestCommonSubstring($str1, $str2);
echo $result; // bcde

使用动态规划的方法：

$str1 = 'abcdefg';
$str2 = 'bcdehijk';
$result = findLongestCommonSubstring($str1, $str2);
echo $result; // bcde

示例2

输入字符串1为“hello world”，字符串2为“world hello”，输出字符串“world”。

使用暴力枚举的方法：

$str1 = 'hello world';
$str2 = 'world hello';
$result = findLongestCommonSubstring($str1, $str2);
echo $result; // worl

使用动态规划的方法：

$str1 = 'hello world';
$str2 = 'world hello';
$result = findLongestCommonSubstring($str1, $str2);
echo $result; // world