最长公共子串

一、最长公共子串和最长公共子序列的区别

最长公共子串：要求子串在原字符串中是连续出现的。 ADE 和ABCDE的最长公共子串是DE

最长公共子序列：不要求子序列在原字符串中是连续的。ADE 和ABCDE的最长公共子序列是ADE

二、最长公共子串

字符串1：caba

字符串2：bab

思路：

1.用一个二维数组存储两个字符串的字符是否相等。对角线上连续为1 的最长的序列即为最长公共子串。

　　b　　a　　b

c 0　　0　　0

a　 0　　1　　0　

b　 1　　0　　1

a　 0　　1　 0

2.如何寻找对角线上连续为1的最长序列？

数组中存储的每一元素的取值为：

若匹配成功，赋值为1加上该元素的左上元素的取值（即上一行中的左邻元素）

若匹配不成功，赋值为0

　　b　　a　　b

c 0　　0　　0

a　 0　　1　　0　

b　 1　　0　　2

a　 0　　2　　0

这样数组中元素的最大值即为最长子序列。

3.存储空间的优化：

在构造这个二维矩阵的过程中，有了当前行之后，上一行的取值就没有用了，因此实际用一个一维数组存储取值即可。

代码如下：

 1 import java.util.Scanner;
 2 
 3 
 4 public class MaxLengthSubString {
 5 
 6     public static void main(String[] args) {
 7         // TODO Auto-generated method stub
 8         Scanner input =new Scanner(System.in);
 9         String s1=input.nextLine();
10         String s2=input.nextLine();
11         System.out.println(new MaxLengthSubString().getMaxLengthSubString(s1, s2));
12     }
13     public static String getMaxLengthSubString(String s1,String s2){
14         int length1=s1.length();
15         int length2=s2.length();
16         int currentArray []=new int[length2];//当前数组  ：用来存储每一次匹配的结果
17         int tempArray []=new int [length2];//临时数组： 用来存储上一次匹配的结果
18         int maxEle=0;
19         int maxElePos=0;//记录最大元素的位置
20         //初始化临时数组和当前数组
21         for (int i = 0; i < length2; i++) {
22             tempArray[i]=0;
23             currentArray[i]=0;
24         }
25         //遍历匹配。
26         for (int i = 0; i < length1; i++) {
27             char c1=s1.charAt(i);
28             for (int j = 0; j < length2; j++) {
29                 char c2=s2.charAt(j);
30                 if(c1==c2){//元素相同
31                     if(j==0){//若是第一列元素相同，则直接赋值为1
32                         currentArray[j]=1;
33                     }else{//若是其他列元素相同，则当前数组的值为：该元素的左上元素的值+1
34                         currentArray[j]=1+tempArray[j-1];
35                     }
36                     //记录最大元素的位置
37                     if(maxEle<currentArray[j]){
38                         maxEle=currentArray[j];
39                         maxElePos=j;
40                     }
41                 }
42             }
43             tempArray=currentArray; //匹配一轮结束之后，当前数组的值成为新的临时数组的值。
44         }
45         
46         String result=s2.substring(maxElePos-maxEle, maxElePos);//最大元素的位置减去公共子串的长度就是公共子串的开始字符的位置。
47         return result;
48     }
49 }