public class CadeiaComumMaisLonga {

    public static int calcularLCS(char [] A, char [] B){
        int [][]LCS = new int [A.length+1][B.length+1];

        for(int i=0;i<=B.length;i++){
            LCS[0][i]=0;
        }

        for(int i=0;i<=A.length;i++){
            LCS[i][0]=0;
        }

        int maxCadeia = 0;

        for(int i=1;i<=A.length;i++){
            for(int j=1;j<=B.length;j++){
                if(A[i-1]==B[j-1]){
                    LCS[i][j] =  LCS[i-1][j-1] +1;
                }else{
                    if(LCS[i-1][j] >= LCS[i][j-1]){
                        LCS[i][j] = LCS[i-1][j];
                    }else{
                        LCS[i][j] = LCS[i][j-1];
                    }
                }

                if(maxCadeia<LCS[i][j]){
                    maxCadeia = LCS[i][j];
                }

                System.out.print(LCS[i][j]);
            }
            System.out.println();
        }

        return maxCadeia;
    }
    public static void main(String[] args) {
        String A = "ACCGGTCGAG";
        String B = "GTCGTTCGGAATGCCGTTGCTCTGT";
        System.out.println("Cadeia comum mais longa : " + calcularLCS(A.toCharArray(), B.toCharArray()));
    }
}