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];
    }


    public char[] getLCSIterative(char[] x, char[] y){
        int[][]matrix=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){
                    matrix[i][j]=0;
                }
                else if(x[i-1]==y[j-1]){
                    matrix[i][j]=1+matrix[i-1][j-1];
                }
                else{
                    matrix[i][j]=Math.max(matrix[i-1][j],matrix[i][j-1]);
                }
            }
        }
        char[] res=new char[matrix[x.length][y.length]];
        int n=x.length;
        int k=y.length;
        int idx=res.length;
        while(n>0 && k>0){
            if(x[n-1]==y[k-1]){
                res[idx-1]=x[n-1];
                idx--;
                n--;
                k--;
            }
            else{
                if(matrix[n-1][k]>matrix[n][k-1]){
                    n--;
                }
                else{
                    k--;
                }
            }
        }
        return res;

    }
}

@@ -206,2063 +206,7 @@
     
-/*%0A    find length of longest common subsequence in recursive way%0A     */%0A    public  int recursiveCount(char%5B%5D x, char%5B%5D y, int xs, int ys)%7B%0A%0A        if(xs==0 %7C%7C ys==0)%7B%0A            return 0;%0A        %7D%0A        else if(x%5Bxs-1%5D==y%5Bys-1%5D)%7B%0A            return 1+recursiveCount(x,y,xs-1,ys-1);%0A        %7D%0A        else %7B%0A            return Math.max(recursiveCount(x,y,xs-1,ys), recursiveCount(x,y,xs,ys-1));%0A        %7D%0A    %7D%0A%0A    public int iterativeTabulationSolution(char%5B%5D x, char%5B%5D y)%7B%0A        int%5B%5D%5B%5Dres=new int%5Bx.length+1%5D%5By.length+1%5D;%0A        for(int i=0; i%3C=x.length; i++)%7B%0A            for(int j=0; j%3C=y.length; j++)%7B%0A                if (i==0 %7C%7C j==0)%7B%0A                    res%5Bi%5D%5Bj%5D=0;%0A                %7D%0A                else if(x%5Bi-1%5D==y%5Bj-1%5D)%7B%0A                    res%5Bi%5D%5Bj%5D=1+res%5Bi-1%5D%5Bj-1%5D;%0A                %7D%0A                else %7B%0A                    res%5Bi%5D%5Bj%5D=Math.max(res%5Bi-1%5D%5Bj%5D,res%5Bi%5D%5Bj-1%5D);%0A                %7D%0A%0A            %7D%0A        %7D%0A        return res%5Bx.length%5D%5By.length%5D;%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+1%5D%5By.length+1%5D;%0A        for(int i=0; i%3C=x.length; i++)%7B%0A            for(int j=0; j%3C=y.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

longest common subsequence- reimplementation