东家蝴蝶西家飞，白骑少年今日归。 愿，所有迷茫的人，都不再迷茫的，愿，所有努力工作的人，都可以得到应有的回报，愿，所有的人，都可以找到回家的方向，愿，再无苦痛，再无离别。
上一章简单介绍了统计字符串中各个字符出现的次数(六),如果没有看过,请观看上一章
一. 最大公共子串
有两个字符串，这两个字符串可能会存在公共的部分，如字符串"abcdef" 和字符串"defg",这两个字符串之间有共同的字符串，“d”,“e”,“f”,“de”,“ef”,“def” 等。最长的公共子串就是"def"。
二.第一种思路，循环找寻
// 如，传递的参数为 "abcdef" 和"defg"
public static String getMaxSubString(String maxString,String minString){
String max=null; //并不知道哪个字符串长，哪个字符串短。
String min=null;
//1。 先找到最大的字符串和最小的字符串。 根据长度进行比较
max=maxString.length()>minString.length()? maxString:minString;
min=maxString.equals(max)?minString:maxString;
//2. 求出最小的那个的长度。 根据这个长度，进行相应的循环。
int minLength=min.length();
//3.如果整个包含的话，那个就不用循环判断了。
if(max.contains(min)){
return min;
}
//3.开始进行相关的循环操作了。
for (int i = 0; i <minLength; i++) { //从最小的开始循环。
// 从开头处开始,最后的位置是minLength; 因为subString 截取时不到后面的那个参数，所以这里是<=minLength;
for(int start=0,end=minLength-i;end<=minLength;start++,end++){
/**
* 第一次循环时， 先看整个是否进行了包含，去掉0位，即defg 是否在abcdef 里面。
* 第二次循环时，要把defg 去掉一位，看是否在abcdef 里面。 截取时，有def 和efg 两种。
* 第三次循环时，把defg 去掉两位。 截取有: de ef fg 三种方式。
* 第四次循环时， 把defg 去掉三位，有 d e f g 四种方式。 如果还不存在，则说明没有相同的子串。
* 外层循环 为最小的字符串的长度。 0~ length_1
* 内层循环为: 从0 开始，结束位置为 length-i, 判断是否在，如果不再，则进行整体移动， 为1 ~length-i+1,2~ length-i+2
* 直到 end 结束位置为 length , 因为substring 时不会取出最后的索引值。
*
*/
String temp=min.substring(start,end); //截取的那个。
if(max.contains(temp)){
return temp;
}
}
}
return null;
}三. LCS (Longest Common Subsequence) 算法
参考教程: 算法的主要原理为:
LCS[i,j] = 0 (i<0||j<0)
LCS(i-1,j-1) (i>=0 && b>0 && (str1[i]==str2[j]))
(1) 构造一个str1.size()*str2.size()的矩阵vec
(2) 如果 str1[i] == str2[j],则vec[i][j] = vec[i-1][j-1]+1;
翻译成中文就是:
将两个字符串分别以行和列组成矩阵。
(2) 计算每个节点行列字符是否相同，如相同则为 1。
(3) 通过找出值为 1 的最长对角线即可得到最长公共子串。
可以进一步的优化:
我们可以将字符相同节点(1)的值加上左上角(d[i-1, j-1])的值，
这样即可获得最大公用子串的长度。如此一来只需以行号和最大值为条件即可截取最大子串。
只需要比较 数组里面的最大值即可了。
程序代码为:
// 如，传递的参数为 "abcdef" 和"defg"
public static String getMaxSubString(String maxString,String minString){
//1. 必须保证 第一个字符串的长度是长的。第二个是短的。
if(minString.length()>maxString.length()){
// 重新调用这个方法
return getMaxSubString2(minString, maxString);
}
//2. 判断一下，是否直接包含，如果是的话，就不用进行阵列转换了。
if(maxString.contains(minString)){
return minString;
}
//3. 取出长度，转换相对应的矩阵。 通常，长的为y,短的为x.
int maxLength=maxString.length();
int minLength=minString.length();
// 构建二维数组
int [][] conver=new int[minLength][maxLength];
int maxValue=0; //最大的值。
int maxIndex=0;//最大的索引。
//4. 对这个矩阵进行相应的放值。
for (int i = 0; i <minLength; i++) {
for(int j=0;j<maxLength;j++){
//5.判断一下，值是否相同。 如果相同，
if(minString.charAt(i)==maxString.charAt(j)){
//相同了，看是第几行，第几列。 第1行或者第1列的为1
if(i==0||j==0){
conver[i][j]=1;
}else{
conver[i][j]=conver[i-1][j-1]+1; //为左上角的值加1.
if(maxValue<conver[i][j]){ // 整个数组的最大值。 也可以是<= < 时表示取第一个，<=为最后一个。(如果存在多个的情况下)
maxValue=conver[i][j]; //取出那个最大的值。
maxIndex=i; //取出那个最大的列索引。
}
}
}else{
conver[i][j]=0; //如果不相同，为0.
}
}
}
//5. 根据最大的索引和最大的值，来判断截取那个最大的子字符串。
if(maxValue!=0&&maxIndex!=0){ // 双重判断，如果有值的话。
// maxIndex 为2 maxValue 为3. 开始处的值为0, 结束处的值为3 (不包括。)
// 变成 值为 2-3+1=0 到3 ， 长度为 2*maxValue-maxIndex-1 =2*3-2-1=3 ,因为不包括maxValue所以不+1了。
return minString.substring(maxIndex-maxValue+1,maxValue);
}
return null;
}谢谢!!!
