package pl.polsl.kamilplewniok;

public class Main {

    private static void printLcs(String b[][], String X, int i,int j){
        if(i==0 || j==0)
            return;
        if(b[i][j].equals("\\")){

            printLcs(b,X,i-1,j-1);
            System.out.println(X.charAt(i));

        }else{
            if(b[i][j].equals("|")){
                printLcs(b,X,i-1,j);
            }else{
                printLcs(b,X,i,j-1);
            }
        }
    }


    public static void main(String[] args) {
        String A = " RJAKMDF";
        String B = " KAJRNCM";
        int c[][] = new int[A.length()][B.length()];
        String b[][] = new String[A.length()][B.length()];

        long startTime = System.nanoTime();

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

        for (int i = 1; i < A.length(); i++) {
            for (int j = 1; j < B.length(); j++) {
                if (A.charAt(i) == B.charAt(j)) {
                    c[i][j] = c[i - 1][j - 1] + 1;
                    b[i][j] = "\\";
                } else {
                    if (c[i - 1][j] >= c[i][j - 1]) {
                        c[i][j] = c[i - 1][j];
                        b[i][j] = "|";
                    } else {
                        c[i][j] = c[i][j - 1];
                        b[i][j] = "-";
                    }
                }
            }
        }
        long endTime = System.nanoTime();
        long time = endTime - startTime;
        printLcs(b,A,A.length()-1,B.length()-1);
        System.out.println("Execution time of in nanoseconds: " + time);
    }
}