求最大公共子串和长度

求最大公共子串和长度问题就是： 求两个串的所有子串中能够匹配上的最长字串和最大长度是多少。 比如：s1="abcdkkk" 和 s2="baabcdadabc"， 可以找到的最长的公共子串是"abcd",最大公共子串长度为4。 输入：

sdgadsgsholjdgadsgop

输出：

6dgadsg

输入：

ssdfjytyjj

输出：

0null

解析：可以用矩阵法进行求解，用s1字符串的每一个字符串和s2中的所有字符进行比较，先定义一个二维数组a[s1长度+1][s2长度+1]，a[i][j]代表的是s1中的一个字符和s2中每一个字符比较的状态，二维数组中一开始默认位置都为0，如果s1和s2对应的位置字符不同，则让a[i][j]为0。如果在对应字符相同的情况下，则看一下对应位置之前的位置即a[i-1][j-1]是不是为0，如果为0则说明则构不成连续子串，否则可以构成连续子串，让a[i][j] = a[i-1][j-1]+1。

代码如下：

public class 最大公共子串{private static String cnt = ""; //最大字串起始为空串public static int Max(String s1,String s2){int max = 0;char[] c1 = s1.toCharArray(); //将s1转换为字符数组char[] c2 = s2.toCharArray(); //将s2转换为字符数组int[][] a = new int[c1.length+1][c2.length+1];//s1中每一个字符都和s2中所有的字符比较for(int i=1,x=a.length;i<x;++i) //a[i][j]代表s1中一个字符和s2中某一个字符的对应位置情况{for(int j=1,y=a[i].length;j<y;++j) //{if(c1[i-1]==c2[j-1])//如果这两个字符相同，该位置+1之前应加上前一个位置的状态{a[i][j] = a[i-1][j-1]+1; }if(a[i][j]>max) //更新最大值{max = a[i][j]; //例如：s1="kkabcdk" 最后一个位置是6//System.out.println(i+" "+j); //i起始值是从1开始的,i代表s1中最大长度字串最后一个字符是第几个cnt = s1.substring(i-max,i);}}}return max;}public static void main(String[] args){Scanner in = new Scanner(System.in);String s1 = in.next();String s2 = in.next();System.out.println(Max(s1,s2)); //最大字串的长度if(cnt==null||cnt==""){System.out.println("null"); //没有匹配到}else{System.out.println(cnt); //最大字串}}}

运行结果：

输入：

sdgadsgsholjdgadsgop

输出：

6dgadsg

输入：

ssdfjytyjj

输出：

0null