求两个字符串的最大公共子串&最长公共子序列
输入：abcbdabbdcaba
4
即 bdcaba 与 abcbdab 的最大公共子串长度为 4
常规思路
枚举法，算出两个字符串的所有子序列，然后分别作比较，选出最大的一个子串
缺点：对于一个长度为 n 的字符串，子串个数有 2 的 n 次方个，然后在依次比较两个字符串的子串，效率过低
动态规划 lcs算法
以动态规划的思想来解这个题，我们用一个二位数组 $dp[][] 来存储各个字符串对应的状态，具体什么含义就不细说了，百度一下，你就知道，主要是用 php 实现一下
代码如下：
functionlcs($str1, $str2){// 存储生成的二维矩阵$dp = array(); // 最大子串长度$max = 0; for ($i = 0; $i $str1); $i++) { for ($j = 0; $j $str2); $j++) { if ($str1[$i] == $str2[$j]) { $dp[$i][$j] = isset($dp[$i-1][$j-1]) ? $dp[$i-1][$j-1] + 1 : 1; } else { $dp[$i-1][$j] = isset($dp[$i-1][$j]) ? $dp[$i-1][$j] : 0; $dp[$i][$j-1] = isset($dp[$i][$j-1]) ? $dp[$i][$j-1] : 0; $dp[$i][$j] = $dp[$i-1][$j] > $dp[$i][$j-1] ? $dp[$i-1][$j] : $dp[$i][$j-1]; } $max = $dp[$i][$j] > $max ? $dp[$i][$j] : $max; } } for ($i = 0; $i $str1); $i++) { for ($j = 0; $j $str2); $j++) { echo$dp[$i][$j] . ; } echo
; } var_dump($max);}lcs(abcbdab, bdcaba);
对应输出：
000111111122112222112233122233122334122344int4
结论：通过动态规划，我们使时间复杂度降为了 o(nm)，但是这样依旧有空间的浪费，有些数据的存储是不必要的，可以进一步做优化
').addclass('pre-numbering').hide(); $(this).addclass('has-numbering').parent().append($numbering); for (i = 1; i ').text(i)); }; $numbering.fadein(1700); }); }); 以上就介绍了lcs算法&最大公共子串&最长公共子序列 php 实现，包括了最长公共子序列,php方面的内容，希望对php教程有兴趣的朋友有所帮助。