public class LCS {

    public static void main(String[] args) {
        String x = "spanking";
        String y = "amputation";
        Stopwatch sw = new Stopwatch();
        int length = dpLCSlength(x, y);
        double time = sw.elapsedTime();
        StdOut.printf("DP LCS length = %d; time = %.3f\n", length, time);
        String lcs = dpLCS(x, y);
        StdOut.printf("LCS = %s\n", lcs);
        Stopwatch sw1 = new Stopwatch();
        int length1 = recursiveLCSlength(x, y);
        double time1 = sw1.elapsedTime();
        StdOut.printf("Recursive LCS length = %d; time = %.3f\n", length1, time1);

    }

    /**
     * Computes a Longest Common Subsequence of x and y
     * 
     * @param x
     * @param y
     * @return an LCS of x and y
     */
    private static String dpLCS(String x, String y) {
        int opt[][] = optimizingTable(x, y);
        StringBuilder sb = new StringBuilder();
        int i = 0, j = 0;
        while(true){
            if (i == x.length()){
                // We know opt[i][j] == 0, so there's nothing more
                break;
            } else if (j == y.length()) {
                // We know opt[i][j] == 0, so there's nothing more
                break;
            } else {
                // To make some progress toward the base, we need to shorten
                // at least one of the suffixes, moving i and/or j toward the end.
                int option1 = opt[i + 1][j]; // skip x[i]
                int option2 = opt[i][j + 1]; // skip y[j]
                // If neither option1 nor option2 is right, option3 must be.
                // The *longest* common subsequence is the maximum of the options.
                if (opt[i][j] == option1) {
                    i++;
                } else if(opt[i][j] == option2) {
                    j++;
                } else {
                    if (x.charAt(i) == y.charAt(j)){
                        // a common character
                        sb.append(x.charAt(i));
                    }
                    i++; j++;
                }
            }

        }
        return sb.toString();
    }

    /**
     * Computes the length of a Longest Common Subsequence (LCS) of x and y
     * 
     * @param x
     * @param y
     * @return the LCS length
     */
    private static int recursiveLCSlength(String x, String y) {
        // Suffixes starting at positions 0 and 0 are the whole strings.
        return recursiveLCSlength(x, y, 0, 0);
    }

    /**
     * Computes the length of a Longest Common Subsequence (LCS) of suffixes of x
     *  and y starting at positions i and j
     * @param x
     * @param y
     * @param i
     * @param j
     * @return the LCS length
     */
    private static int recursiveLCSlength(String x, String y, int i, int j) {
        if (i == x.length()){
            return 0;
        } else if (j == y.length()) {
            return 0;
        } else {
            // To make some progress toward the base, we need to shorten
            // at least one of the suffixes, moving i and/or j toward the end.
            int option1 = recursiveLCSlength(x, y, i + 1, j); // skip x[i]
            int option2 = recursiveLCSlength(x, y, i, j + 1); // skip y[j]
            int option3 = recursiveLCSlength(x, y, i + 1, j + 1); // skip both?
            if (x.charAt(i) == y.charAt(j)) {
                option3 += 1; // 1 character in common
            }
            // The *longest* common subsequence is the maximum of the options.
            return Math.max(option1, Math.max(option2, option3));
        }
    }
    
    /**
     * Computes the length of a Longest Common Subsequence (LCS) of x and y
     * 
     * @param x
     * @param y
     * @return the LCS length
     */
    private static int dpLCSlength(String x, String y) {
        // opt[i][j] contains the same value as recursiveLCSlength(x, y, i, j)
        int[][] opt = optimizingTable(x, y);
        // Suffixes starting at positions 0 and 0 are the whole strings.
        return opt[0][0];
    }

    /**
     * Produces table of the LCS lengths for all suffixes of x and y
     * 
     * @param x
     * @param y
     * @return table with position [i][j] being for suffixes starting at i and j
     */
    private static int[][] optimizingTable(String x, String y) {
        int[][] opt = new int[x.length() + 1][y.length() + 1];
        for(int i = x.length(); i >= 0; i--) {
            for(int j = y.length(); j >= 0; j--) {
                if (i == x.length()){
                    opt[i][j] = 0;
                } else if (j == y.length()) {
                    opt[i][j] = 0;
                } else {
                    // To make some progress toward the base, we need to shorten
                    // at least one of the suffixes, moving i and/or j toward the end.
                    int option1 = opt[i + 1][j]; // skip x[i]
                    int option2 = opt[i][j + 1]; // skip y[j]
                    int option3 = opt[i + 1][j + 1]; // skip both?
                    if (x.charAt(i) == y.charAt(j)) {
                        option3 += 1; // 1 character in common
                    }
                    // The *longest* common subsequence is the maximum of the options.
                    opt[i][j] = Math.max(option1, Math.max(option2, option3));
                }
            }
        }
        return opt;
    }

}