动态规划最长公共子串

我就是我 2021-08-11 20:24 422阅读 0赞

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

最长公共子串同样是构造二维数组存储最大值，只不过去掉了取上方左方较大值的哪一步，这样就保证了连续，只有通过左上加1增加最大值。  
同样他的读取也相对简单，找到最大值，直接顺左上方向读取即可

![5057999-aadc452cd4a194c7.png][]

如图所示

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);
             }
         }

[Link 1]: https://www.jianshu.com/p/8624ec269760
[5057999-aadc452cd4a194c7.png]: /images/20210811/28d3459fbaa34efe9855b653bbe9c4b9.png