[알고리즘] LCS (최장 공통 부분) 찾기

public class Main {



    public static void main(String[] args) {

        String x = "abcdedc";
        String y = "bbbcec";

        int c[][] = new int[x.length()][y.length()];
        String lcs[][] = new String[x.length()][y.length()];

        for(int i = 0;i< lcs.length;i++)
            for(int j = 0;j<lcs[i].length;j++)
                lcs[i][j] = "";

        for(int i = 1; i < x.length();i++)
        {
            for(int j = 1;j < y.length();j++)
            {
                if(x.charAt(i) == y.charAt(j))
                {
                    c[i][j] = c[i-1][j-1]+1;
                    lcs[i][j] = lcs[i-1][j-1] + x.charAt(i);
                }
                else
                {
                    if(c[i-1][j] > c[i][j-1])
                    {
                        c[i][j] = c[i-1][j];
                        lcs[i][j] = lcs[i-1][j];
                    }
                    else
                    {
                        c[i][j] = c[i][j-1];
                        lcs[i][j] = lcs[i][j-1];
                    }
                }
            }
        }

        System.out.println(c[x.length()-1][y.length()-1]);
        System.out.println(lcs[x.length()-1][y.length()-1]);

        /*결과 :
        4
        bcec
        */
    }


}

 동적 프로그래밍 사용