1、 首先区别最长公共子串和最长公共子序列 找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。 2、 最长公共子串 其实这是一个序贯决策问题，可以用动态规划来求解。使用一个二维矩阵来记录中间结果。 eg： abcd和bca
| 列 | a | b | c | d |
|---|---|---|---|---|
| b | 0 | 1 | 0 | 0 |
| c | 0 | 0 | 2 | 0 |
| a | 1 | 0 | 0 | 0 |
不多说，上代码
public class Solution { /** * @param A, B: Two string. * @return: the length of the longest common substring. */ public int longestCommonSubstring(String A, String B) { // write your code here int max=0;//记录最长子串的大小 char[] AStr=A.toCharArray(); char[] BStr=B.toCharArray(); int lenA=AStr.length; int lenB=BStr.length; int x=0,y=0;//记录最长子串结束的位置 int a[][]=new int[lenA][lenB];//初始化矩阵 for(int i=0;i<lenA;i++){ for(int j=0;j<lenB;j++){ if(AStr[i]==BStr[j]){ if(i==0||j==0){ a[i][j]=1; }else{ a[i][j]=a[i-1][j-1]+1; } if(a[i][j]>max){ max=a[i][j]; x=i; y=j; } } else a[i][j]=0; } } return max; }}附：我看到还有一维数组来做的例子，但是我觉得二维比较容易理解，但还是贴下代码 以下代码来自： https://my.oschina.net/leejun2005/blog/117167
public class LCString2 { public static void getLCString(char[] str1, char[] str2) { int i, j; int len1, len2; len1 = str1.length; len2 = str2.length; int maxLen = len1 > len2 ? len1 : len2; int[] max = new int[maxLen]; int[] maxIndex = new int[maxLen]; int[] c = new int[maxLen]; // 记录对角线上的相等值的个数 for (i = 0; i < len2; i++) { for (j = len1 - 1; j >= 0; j--) { if (str2[i] == str1[j]) { if ((i == 0) || (j == 0)) c[j] = 1; else c[j] = c[j - 1] + 1; } else { c[j] = 0; } if (c[j] > max[0]) { // 如果是大于那暂时只有一个是最长的,而且要把后面的清0; max[0] = c[j]; // 记录对角线元素的最大值，之后在遍历时用作提取子串的长度 maxIndex[0] = j; // 记录对角线元素最大值的位置 for (int k = 1; k < maxLen; k++) { max[k] = 0; maxIndex[k] = 0; } } else if (c[j] == max[0]) { // 有多个是相同长度的子串 for (int k = 1; k < maxLen; k++) { if (max[k] == 0) { max[k] = c[j]; maxIndex[k] = j; break; // 在后面加一个就要退出循环了 } } } } } for (j = 0; j < maxLen; j++) { if (max[j] > 0) { System.out.PRintln("第" + (j + 1) + "个公共子串:"); for (i = maxIndex[j] - max[j] + 1; i <= maxIndex[j]; i++) System.out.print(str1[i]); System.out.println(" "); } } } public static void main(String[] args) { String str1 = new String("123456abcd567"); String str2 = new String("234dddabc45678"); // String str1 = new String("aab12345678cde"); // String str2 = new String("ab1234yb1234567"); getLCString(str1.toCharArray(), str2.toCharArray()); }}新闻热点
疑难解答
