LCS, Longest Common Substring, Longest Common Subsequence 알고리즘

LCS(Longest Common Substring,Subsequence) 최장 부분 문자열

최장 부분 문자열 은 두가지 형태가 존재,

Substring은 연속적인 부분 문자열,

Subsequence는 불연속 적이어도 되는 부분 문자열

 

 Substring을 구하는 방법은 동적 계획법으로 간단하게 해결가능,

 

	String str1 = br.readLine();
        String str2 = br.readLine();
        int ans=0;
        int[][] dp = new int[str1.length()+1][str2.length()+1];
        for(int i=1; i<=str1.length(); i++){
            for(int j=1; j<=str2.length(); j++){
                if(str1.charAt(i-1)==str2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    if(ans < dp[i][j]){
                        ans = dp[i][j];
                    }
                }
            }
        }

연속적으로 같은 문자열만 이전 연속 문자열 길이에 + 1 해줌

 

Subsequence를 구하는 방법은 각 문자열에 앞에 "0"을 추가하고 테이블을 만들어서 해결

두 문자열을 테이블로 구성하고 각 문자마다 같은지 비교,

같은 문자면, 왼쪽 대각선 길이 + 1,

다른 문자면, 왼쪽 or 위 쪽 길이 중 큰값

LCS문자열의 길이 뿐 아니라 문자열까지 구하고 싶다면,

길이를 구할때 해당 테이블 값이 대각선 + 1 인지 왼쪽 혹은 위쪽 길이 인지 체크해주고,

체크된 값을 사용해서 테이블의 가장 끝에서부터 추적해 감, 대각선 + 1 한 값이면 LCS문자열에 추가해줌

(테이블에서 가장 큰값부터 작은값으로 역추적 하는 느낌)

	String str1 = "0"+br.readLine();
        String str2 = "0"+br.readLine();
        int[][] lcs = new int[str2.length()][str1.length()];
        String[][] dir = new String[str2.length()][str1.length()];
        int len=0;

        //길이 구하기
        for(int i=1; i<str2.length(); i++){
            for(int j=1; j<str1.length(); j++){
                if(str2.charAt(i)==str1.charAt(j)){//같은 문자면 왼쬑 위 대각선 길이 + 1
                    lcs[i][j] = lcs[i-1][j-1] + 1;
                    dir[i][j] = "diagonal";
                }
                else{
                    lcs[i][j] = Math.max(lcs[i][j-1],lcs[i-1][j]); //다른 문자면 왼쪽 혹은 위 쪽 길이 중 큰값
                    if(lcs[i][j]==lcs[i][j-1]){
                        dir[i][j] = "left";
                    }
                    else{
                        dir[i][j] = "up";
                    }
                }
                if(len < lcs[i][j])
                    len = lcs[i][j];
            }
        }

        //lcs 문자열 구하기
        int i = str2.length()-1;
        int j = str1.length()-1;
        StringBuilder ans = new StringBuilder();
        while(dir[i][j] != null){
            if(dir[i][j]=="diagonal"){// 대각선 이면 lcs문자열에 추가
                ans.append(str1.charAt(j));
                i--;
                j--;
            }
            else{
                if(dir[i][j]=="left"){//왼쪽으로 이동
                    j--;
                }
                else{//위쪽으로 이동
                    i--;
                }
            }
        }
        ans.reverse().toString();

참고 사이트:

https://twinw.tistory.com/126

LCS(Longest Common Subsequence) 알고리즘

https://mygumi.tistory.com/126

LCS(최장 공통 부분 수열) 알고리즘 :: 마이구미