常考数据结构与算法:最长公共子串

题目描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。

 

示例1

输入

"1AB2345CD","12345EF"

返回值

"2345"

 

思路

1、把两个字符串分别以行和列组成一个二维矩阵。

2、比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0。

3、通过查找出值为1的最长对角线就能找到最长公共子串。

 

比如：str=acbcbcef，str2=abcbced，则str和str2的最长公共子串为bcbce，最长公共子串长度为5。

针对于上面的两个字符串我们可以得到的二维矩阵如下：

从上图可以看到，str1和str2共有5个公共子串，但最长的公共子串长度为5。

为了进一步优化算法的效率，我们可以再计算某个二维矩阵的值的时候顺便计算出来当前最长的公共子串的长度，即某个二维矩阵元素的值由record[i][j]=1演变为record[i][j]=1 +record[i-1][j-1]，这样就避免了后续查找对角线长度的操作了。修改后的二维矩阵如下：

递推公式为：

当A[i] != B[j]，dp[i][j] = 0

当A[i] == B[j]，

若i = 0 || j == 0，dp[i][j] = 1

否则 dp[i][j] = dp[i - 1][j - 1] + 1

 

代码

public class LCSMe {public static void main(String[] args) {String str1 = "1AB2345CD";String str2 = "12345EF";LCSMe lcsMe = new LCSMe();String ret = lcsMe.LCSdp(str1,str2);System.out.println(ret);}/*** 暴力破解** longest common substring* @param str1 string字符串 the string* @param str2 string字符串 the string* @return string字符串*/public String LCS (String str1, String str2) {char[] ch1 = str1.toCharArray();char[] ch2 = str2.toCharArray();String maxStr = "";String strTmp = "";int maxCount = 0;int count = 0;for (int i = 0; i < ch1.length; i++) {for (int j = 0; j < ch2.length; j++) {count = 0;strTmp = "";for (int k = i,x=j; k < ch1.length&&x<ch2.length; k++,x++) {if(ch1[k] == ch2[x]){count++;strTmp += ch1[k];}else{break;}}if(count > maxCount){maxCount = count;}if(strTmp.length() > maxStr.length()){maxStr = strTmp;}}}return maxStr;}/*** 动态规划dynamic programming** longest common substring* @param str1 string字符串 the string* @param str2 string字符串 the string* @return string字符串*/public String LCSdp (String str1, String str2) {int[][] dp = new int[str1.length()+ 1][str2.length() + 1];char[] ch1 = str1.toCharArray();char[] ch2 = str2.toCharArray();String maxStr = "";String strTmp = "";int maxCount = 0;int count = 0;int maxI = 1;int maxJ = 1;for (int i = 1; i <= ch1.length; i++) {for (int j = 1; j <= ch2.length; j++) {if(ch1[i-1] == ch2[j-1]){dp[i][j] = dp[i - 1][j - 1] + 1;//maxCount = Math.max(dp[i][j], maxCount);if(dp[i][j] > maxCount){maxCount = dp[i][j];maxI = i;maxJ = j;}}}}maxI -= dp[maxI][maxJ];maxJ -= dp[maxI][maxJ];for (int i = 0; i < maxCount; i++,maxI++) {maxStr += ch1[maxI];}return maxStr;} }

 

《新程序员》：云原生和全面数字化实践50位技术专家共同创作，文字、视频、音频交互阅读

总结

以上是生活随笔为你收集整理的常考数据结构与算法:最长公共子串的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。