package com.problems.geeksforgeeks;

/**
 * Created by Maks on 5/31/2017.
 * http://www.geeksforgeeks.org/dynamic-programming-set-4-longest-common-subsequence/
 */
public class LongestCommonSubsequence {

    /*
    find length of longest common subsequence in recursive way
     */
    public  int recursiveCount(char[] x, char[] y, int xs, int ys){

        if(xs==0 || ys==0){
            return 0;
        }
        else if(x[xs-1]==y[ys-1]){
            return 1+recursiveCount(x,y,xs-1,ys-1);
        }
        else {
            return Math.max(recursiveCount(x,y,xs-1,ys), recursiveCount(x,y,xs,ys-1));
        }
    }

    public int iterativeTabulationSolution(char[] x, char[] y){
        int[][]res=new int[x.length+1][y.length+1];
        for(int i=0; i<=x.length; i++){
            for(int j=0; j<=y.length; j++){
                if (i==0 || j==0){
                    res[i][j]=0;
                }
                else if(x[i-1]==y[j-1]){
                    res[i][j]=1+res[i-1][j-1];
                }
                else {
                    res[i][j]=Math.max(res[i-1][j],res[i][j-1]);
                }

            }
        }
        return res[x.length][y.length];
    }
}

@@ -1190,10 +1190,1073 @@
 ;%0A    %7D%0A
+%0A%0A    public char%5B%5D getLCSIterative(char%5B%5D x, char%5B%5D y)%7B%0A        int%5B%5D%5B%5Dmatrix=new int %5Bx.length%5D%5By.length%5D;%0A        for(int i=0; i%3Cx.length; i++)%7B%0A            for(int j=0; j%3Cy.length; j++)%7B%0A                if(i==0 %7C%7C j==0)%7B%0A                    matrix%5Bi%5D%5Bj%5D=0;%0A                %7D%0A                else if(x%5Bi-1%5D==y%5Bj-1%5D)%7B%0A                    matrix%5Bi%5D%5Bj%5D=1+matrix%5Bi-1%5D%5Bj-1%5D;%0A                %7D%0A                else%7B%0A                    matrix%5Bi%5D%5Bj%5D=Math.max(matrix%5Bi-1%5D%5Bj%5D,matrix%5Bi%5D%5Bj-1%5D);%0A                %7D%0A            %7D%0A        %7D%0A        char%5B%5D res=new char%5Bmatrix%5Bx.length%5D%5By.length%5D%5D;%0A        int n=x.length;%0A        int k=y.length;%0A        int idx=res.length;%0A        while(n%3E0 && k%3E0)%7B%0A            if(x%5Bn-1%5D==y%5Bk-1%5D)%7B%0A                res%5Bidx-1%5D=x%5Bn-1%5D;%0A                idx--;%0A                n--;%0A                k--;%0A            %7D%0A            else%7B%0A                if(matrix%5Bn-1%5D%5Bk%5D%3Ematrix%5Bn%5D%5Bk-1%5D)%7B%0A                    n--;%0A                %7D%0A                else%7B%0A                    k--;%0A                %7D%0A            %7D%0A        %7D%0A        return res;%0A%0A    %7D%0A
 %7D%0A

iterative solution print common longest subsequence