核心思路和最长公共子序列一样 区别在于子串必须连续 可以先看我之前这篇文章
最长公共子序列问题总结
最长公共子串同样是构造二维数组存储最大值，只不过去掉了取上方左方较大值的哪一步，这样就保证了连续，只有通过左上加1增加最大值。
同样他的读取也相对简单，找到最大值，直接顺左上方向读取即可
如图所示
public static String LCS(int[][] c,char[] x, char[] y) {
int m=x.length;
int n=y.length;
int max=0,end=0;
for(int i=0;i<=m;i++)
c[i][0]=0;
for(int j=0;j<=n;j++)
c[0][j]=0;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++){
if(x[i-1]==y[j-1]){
c[i][j]=c[i-1][j-1]+1;
if(c[i][j]>max){
max=c[i][j];
end=j;
}
}
else {
c[i][j]=0;
}
}
StringBuilder sb=new StringBuilder();
for(int j=end-max;j<end;j++){//c数组的x,y均多一，计算时候要注意
sb.append(y[j]);
}
return sb.toString();
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
String x=sc.nextLine();
String y=sc.nextLine();
int[][] c=new int[x.length()+1][y.length()+1];
String s=LCS(c,x.toCharArray(),y.toCharArray());
System.out.println(s);
}
}
