求两个字符串的最大连续公共字串

如下两个字符串,公共连续字符串为abcdf，求出这个abcdf，

"aaffffsfabcdfasf", "aaaadfsabcdfsdb"

假设字符串长度分别为m,n，这个题有个m*n*min(m,n)复杂度的方法，这个方法比较慢，暂时不考虑。

另一个种方法是动态规划：

设置二维数组dp[][], dp[i][j]==0表示第一个字符串的第i个字符与第二个字符串的第j个字符不相等，dp[i][j]!=0表示第一个字符串的第i个字符与第二个字符串的第j个字符串相等，并且，如果dp[i][j]==k，不仅当前字符相等，前面k-1个也相等，也就是dp的公式为dp[i][j] = dp[i-1][j-1]+1。最终二维矩阵的结果如下所示（随机写的）：

00010010

01000000

00201000

01030010

11014101

代码如下：

//求两个字符串的最大公共字串 public String longestSerialSubstring(String s1,String s2){ String res = ""; int m = s1.length(),n = s2.length(); int[][] dp = new int[m][n]; int max = 0; int index = 0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ char c1 = s1.charAt(i); char c2 = s2.charAt(j); if(c1==c2){ if(i==0 || j==0){ dp[i][j] = 1; }else{ dp[i][j] = dp[i-1][j-1] + 1; } if(dp[i][j]>max){ max = dp[i][j]; index = i; } } } } res = s1.substring(index-max+1,index+1); return res; }