博客

public class LCS {
    public int longestCommonString(String a, String b){
        int result = 0;
        int[][] temp = new int[a.length()][b.length()];
        for(int i = 0 ; i < a.length() ; i++){
            for(int j = 0 ; j < b.length() ; j++){
                if(a.charAt(i) == b.charAt(j)){
                    if(i == 0 || j == 0)
                        temp[i][j] = 1;
                    else
                        temp[i][j] = temp[i-1][j-1] + 1;
                    if(temp[i][j] > result)
                        result = temp[i][j];
                }else{
                    temp[i][j] = 0;
                }
            }
        }

        print(temp, a, b);
        return result;
    }

    public void print(int[][] temp, String a, String b){
        for(int i = 0 ; i < a.length() ; i++){
            for(int j = 0 ; j < b.length() ; j++){
                System.out.print(temp[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        LCS lcs = new LCS();
        int result = lcs.longestCommonString("abc123ddd", "234ddd");
        System.out.println(result);
    }
}

执行结果如下

0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
1 0 0 0 0 0 
0 2 0 0 0 0 
0 0 0 1 1 1 
0 0 0 1 2 2 
0 0 0 1 2 3 
3