LCS算法&最大公共子串&最长公共子序列PHP实现最长公共上升子序列最长公共子序列c语言最长公共递增子序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LCS算法&最大公共子串&最长公共子序列PHP实现最长公共上升子序列最长公共子序列c语言最长公共递增子序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1546字,纯文字阅读大概需要3分钟。
内容图文
![LCS算法&最大公共子串&最长公共子序列PHP实现最长公共上升子序列最长公共子序列c语言最长公共递增子序](/upload/InfoBanner/zyjiaocheng/159/06108e389e1a41e4af57b6901a3627c0.jpg)
输入:
abcbdab
bdcaba
4
即
bdcaba
与abcbdab
的最大公共子串长度为 4
常规思路
枚举法,算出两个字符串的所有子序列,然后分别作比较,选出最大的一个子串
缺点:对于一个长度为 n 的字符串,子串个数有 2 的 n 次方个,然后在依次比较两个字符串的子串,效率过低
动态规划 LCS算法
以动态规划的思想来解这个题,我们用一个二位数组 $dp[][]
来存储各个字符串对应的状态,具体什么含义就不细说了,百度一下,你就知道,主要是用 PHP 实现一下
代码如下:
functionlcs($str1, $str2)
{// 存储生成的二维矩阵$dp = array();
// 最大子串长度$max = 0;
for ($i = 0; $i < strlen($str1); $i++) {
for ($j = 0; $j < strlen($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 < strlen($str1); $i++) {
for ($j = 0; $j < strlen($str2); $j++) {
echo$dp[$i][$j] . " ";
}
echo"
";
}
var_dump($max);
}
lcs("abcbdab", "bdcaba");
对应输出:
000111111122112222112233122233122334122344int4
').addClass('pre-numbering').hide(); $(this).addClass('has-numbering').parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($('').text(i)); }; $numbering.fadeIn(1700); }); });结论:通过动态规划,我们使时间复杂度降为了 O(nm),但是这样依旧有空间的浪费,有些数据的存储是不必要的,可以进一步做优化
以上就介绍了LCS算法&最大公共子串&最长公共子序列 PHP 实现,包括了最长公共子序列,php方面的内容,希望对PHP教程有兴趣的朋友有所帮助。
内容总结
以上是互联网集市为您收集整理的LCS算法&最大公共子串&最长公共子序列PHP实现最长公共上升子序列最长公共子序列c语言最长公共递增子序全部内容,希望文章能够帮你解决LCS算法&最大公共子串&最长公共子序列PHP实现最长公共上升子序列最长公共子序列c语言最长公共递增子序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。