最长公共子串

一个字符串A的子串被定义成从A中顺次选出若干个字符构成的串。如A=“cdaad” ,顺次选1，3，5个字符就构成子串” cad” ,现给定两个字符串，求它们的最长共公子串。

输入格式：第一行两个字符串用空格分开。

输出格式：最长子串的长度。

两个串的长度均小于2000

样例输入

abccd aecd
样例输出

3

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new  Scanner(System.in);
        String str1=sc.next();
        String str2=sc.next();
        char [] x=new char[str1.length()+1];
        char [] y=new char[str2.length()+1];
        char []arr1=str1.toCharArray();
        char []arr2=str2.toCharArray();
        for (int i = 0; i <arr1.length; i++) {
            x[i+1]=arr1[i];
        }
        for (int i = 0; i <arr2.length; i++) {
            y[i+1]=arr2[i];
        }
        int [][] c=new int [x.length][y.length];
        int [][] b=new int [x.length][y.length];
        LCSLength(x.length-1, y.length-1, x, y, c, b);
        System.out.println(c[x.length-1][y.length-1]);
        LCS(x.length-1, y.length-1, x, b);
    }
    public static void LCSLength(int m,int n,char [] x,char [] y,int [][]c,int [][] b){
        int i,j;
        for ( i = 1; i <=m; i++) {
            c[i][0]=0;
        }

        for ( i = 1; i <=n; i++) {
            c[0][i]=0;
        }

        for ( i = 1; i <=m; i++) {
            for ( j = 1; j <=n; j++) {
                if(x[i]==y[j]){
                    c[i][j]=c[i-1][j-1]+1;
                    b[i][j]=1;
                }else if(c[i-1][j]>=c[i][j-1]){
                    c[i][j]=c[i-1][j];
                    b[i][j]=2;
                }else{
                    c[i][j]=c[i][j-1];
                    b[i][j]=3;
                }
            }
        }
    }

    public static void LCS(int i,int j,char [] x,int [][]b){
        if(i==0||j==0){return;}
        if(b[i][j]==1){
            LCS(i-1,j-1,x,b);
            System.out.print(x[i]);
        }else if(b[i][j]==2){
            LCS(i-1,j,x,b);
        }else{
            LCS(i,j-1,x,b);
        }
}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61