动态规划 最长公共子串

核心思路和最长公共子序列一样 区别在于子串必须连续 可以先看我之前这篇文章
最长公共子序列问题总结

最长公共子串同样是构造二维数组存储最大值，只不过去掉了取上方左方较大值的哪一步，这样就保证了连续，只有通过左上加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);
         }
     }