PHP算法之PHP实现最长公共子串的问题

内容导读

收集整理的这篇技术教程文章主要介绍了PHP算法之PHP实现最长公共子串的问题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2805字，纯文字阅读大概需要5分钟。

内容图文

本篇文章给大家带来的内容是PHP算法之PHP实现最长公共子串的问题。有一定的参考价值，有需要的朋友可以参考一下，希望对你们有所助。

最长公共子串问题：

给定两个字符串，求出它们之间最长的相同子字符串的长度。

暴力解法思路：

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            ++m            ++n        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实现最长公共子串的问题的详细内容，更多请关注Gxl网其它相关文章！

内容总结

以上是为您收集整理的PHP算法之PHP实现最长公共子串的问题全部内容，希望文章能够帮你解决PHP算法之PHP实现最长公共子串的问题所遇到的程序开发问题。 如果觉得技术教程内容还不错，欢迎将网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。