最长公共子串问题:
给定两个字符串,求出它们之间最长的相同子字符串的长度。
暴力解法思路:
1.以两个字符串的每个字符为开头,往后比较,这样就会需要两层循环
2.两层循环内部的比较方式,也是一层循环,以当前字符为起点,往后遍历比较,直到有不同就跳出这次循环,记录下相同子字符串的长度
3.以最长的那次长度为准,因此也就是有三层循环。时间复杂度O(n^3)
longest=0for i=0;i str1.size;i++ for j=0;j str2.size;j++ m=i n=j length=0 while(m str1.size n str2.size) if str1[m]!=str2[n] break ++length longest=longest length ? length:longest
动态规划法:
1.上面的比较过程中,以i和j为起点开始,如果遇到不同的停止后,下一次的开始位置会进行重复比较
2.动态规划法-空间换时间,矩阵图,可以把复杂度降至O(n^2)
3.str1是横轴,str2是纵轴,table[i][j]就是以这两个字符为结尾的最长子串的长度
4.table[0][j]可以推出,如果str1[0]==str2[j]的就为1,table[i][0]可以推出,如果str1[i]==str2[0] 就为1,其余为0
5.table[i][j] 如果str1[i]==str2[j] 可以由table[i-1][j-1]+1得到,不等就为0
假设两个字符串分别为s和t,s[i]和t[j]分别表示其第i和第j个字符(字符顺序从0开始),再令L[i, j]表示以s[i]和s[j]为结尾的相同子串的最大长度。应该不难递推出L[i, j]和L[i+1,j+1]之间的关系,因为两者其实只差s[i+1]和t[j+1]这一对字符。若s[i+1]和t[j+1]不同,那么L[i+1, j+1]自然应该是0,因为任何以它们为结尾的子串都不可能完全相同;而如果s[i+1]和t[j+1]相同,那么就只要在以s[i]和t[j]结尾的最长相同子串之后分别添上这两个字符即可,这样就可以让长度增加一位。合并上述两种情况,也就得到L[i+1,j+1]=(s[i]==t[j]?L[i,j]+1:0)这样的关系。
代码实例:
?php$str1= abcdef $str2= esdfdbcde1 //暴力解法function longestCommonSubstring1($str1,$str2){ $longest=0; $size1=strlen($str1); $size2=strlen($str2); for($i=0;$i $size1;$i++){ for($j=0;$j $size2;$j++){ $m=$i; $n=$j; $length=0; while($m $size1 $n $size2){ if($str1[$m]!=$str2[$n]) break; ++$length; ++$m; ++$n; $longest=$longest $length ? $length : $longest; return $longest;//矩阵动态规划法function longestCommonSubstring2($str1,$str2){ $size1=strlen($str1); $size2=strlen($str2); $table=array(); for($i=0;$i $size1;$i++){ $table[$i][0]=$str1[$i]==$str2[0] ? 1:0; for($j=0;$j $size2;$j++){ $table[0][$j]=$str1[0]==$str2[$j] ? 1:0; for($i=1;$i $size1;$i++){ for($j=1;$j $size2;$j++){ if($str1[$i]==$str2[$j]){ $table[$i][$j]=$table[$i-1][$j-1]+1; }else{ $table[$i][$j]=0; $longest=0; for($i=0;$i $size1;$i++){ for($j=0;$j $size2;$j++){ $longest=$longest $table[$i][$j] ? $table[$i][$j] : $longest; return $longest;$len=longestCommonSubstring1($str1,$str2);$len=longestCommonSubstring2($str1,$str2);var_dump($len);
以上就是本篇的全部内容,更多相关教程请访问php编程从入门到精通全套视频教程,php实战视频教程,bootstrap视频教程!
以上就是PHP算法之PHP实现最长公共子串的问题的详细内容,PHP教程
郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。
新闻热点
疑难解答