public class Main {

    public static void getLCS(String x, String y) {
        int m = x.length();
        int n = y.length();
        int[][] Mango = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                if (i == 0 || j == 0)
                    Mango[i][j] = 0;
                else if (x.charAt(i - 1) == y.charAt(j - 1))
                    Mango[i][j] = 1 + Mango[i - 1][j - 1];
                else
                    Mango[i][j] = Math.max(Mango[i - 1][j], Mango[i][j - 1]);

            }
        }
        //printLCS
        int index = Mango[m][n];
        int tmp = index;

        char[] lcs = new char[index + 1];
        lcs[index] = ' ';

        int i = m, j = n;

        while(i > 0 && j > 0) {
            if (x.charAt(i - 1) == y.charAt(j - 1)) {
                lcs[index - 1] = x.charAt(i - 1);
                i--;
                j--;
                index--;
            }
            else if (Mango[i - 1][j] > Mango[i][j - 1])
                i--;
            else
                j--;
        }
        System.out.print("NWP: ");
        for (int k = 0; k <= tmp; k++)
            System.out.print(lcs[k]);
        System.out.println("\nDługość NWP = " + Mango[m][n] + "\n");
    }

    public static void main(String[] chars){

        String un = "abccaba";
        String deux = "cabacaa";
        getLCS(un,deux);

        String trois = "abcbdab";
        String quatre = "bdcaba";
        getLCS(trois,quatre);

        String cinq = "stachu";
        String six = "shcu";
        getLCS(cinq,six);

        String sept = "abcb";
        String huit = "bdacb";
        getLCS(sept,huit);
    }
}