求两个字符串的最长公共字符串

 2018-12-19 12:01:22   {{zan}}   0   248 

求最长公共字符串

题目描述:

        求两个字符串的最长公共字符串,例如随便给出两个字符串,得出所有的公共最长的字符。否则返回NULL。

        例如:若 a =“ qwer123456 ”,b =“ qwe123456  ”,则函数返回“123456”。

实现思路:

        思路:利用动态规划和矩阵的思想。

        动态规划:就是用空间的代价来争取时间,将中间结果保存下来,后面循环使用供,减少重复计算次数。
        矩阵思想:定义一个矩阵,宽和高分别为两个字符串的长度。从上到下、从左到右逐个扫描,每次扫描要比较矩阵中每个点对应的行列字符是否相等, 相等的话等于左上邻+1,不相等则置为0。
        时间复杂度:矩阵中的长和宽的乘积即为复杂度。复杂度为O(mn)。
        如两个字符串:“abcd”和“ebc”。如下所示:

           a b c d
        e 0 0 0 0
        b 0 1 0 0
        c 0 0 2 0  

需要注意:为什么相等的话要等于左上邻+1?因为左上邻代表两个字符串的各自前一个元素,如果前一个元素是对应相等的,且当前位置的对应元素也相等,那么公共字符串的长度需要+1,因此等于左上邻+1。

代码实现:

function getLongestSameStr($a, $b)
{
if (empty($a) || empty($b)) return 0;
// 判断字符串是否包含
if (strlen($a) > strlen($b)) {
if (strstr($a, $b) != '') return $b;
} else {
if (strstr($b, $a) != '') return $a;
}

$same_arr = [];// 矩阵
$same_str = [];// 所有相同的字符串
$a_len = strlen($a);
$b_len = strlen($b);
$longest_str = 0;// 最长的字符串
for ($i = 0; $i < $a_len; $i++) {
for ($j = 0; $j < $b_len; $j++) {
if ($a[$i] == $b[$j]) {
if ($i > 0 && $j > 0) {
$same_arr[$i][$j] = $same_arr[$i - 1][$j - 1] + 1;
} else {
$same_arr[$i][$j] = 1;
}
// 所有相同长度的字符串
$longest_str = max($longest_str, $same_arr[$i][$j]);
$same_str[] = substr($a, $i - $same_arr[$i][$j] + 1, $same_arr[$i][$j]);
} else {
$same_arr[$i][$j] = 0;
}
}
}
// 最长的相同字符串
$longest_same_str = [];
foreach ($same_str as $v) {
if ($longest_str == strlen($v)) {
$longest_same_str[] = $v;
}
}
return $longest_same_str;
}

函数调用:

$a = '11111111abced3212334123wqeqwe156123456789';
$b = '111222abced3213346262qweqweqweqwe64123456789';
$aaa = getLongestSameStr($a, $b);
echo '<pre>';
print_r($aaa);

输出结果:

Array
(
[0] => 123456789
)
假如设定特殊的字符串,如$a和$b有两个公共的相同长度的字符串,调用次函数后会出现两个字符串。  
$a = '11111111abced321334123wqeqwa12345678901';
$b = '111222abced3213346262qweqweqweqweb12345678901';
$aaa = getLongestSameStr($a, $b);
echo '<pre>';
print_r($aaa);

输出结果如下:

Array
(
[0] => abced321334
[1] => 12345678901
)

达到了预期的效果。

最后总结:

        此算法由本人自行编写,并调试成功,转载请标注,谢谢!如有问题,欢迎指正!


千而の大狮子!

本文链接地址:https://caohongyuan.cn/p?id=65

(邮箱不会公开,只会做回复通知用) 提交 清空 {{comment.content}}
Re:{{response.content}}