공통 부분 문자열(백준_5582)

https://www.acmicpc.net/problem/5582

5582번: 공통 부분 문자열

문제 설명

2개의 문자열이 주어지면 2개의 문자열에 모두 포함 된  부분문자열 중 가장 긴 것의 길이를 출력하는 것이다.

ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR이 존재한다. 이 중 제일 긴 문자열의 길이는 5이기 때문에 답은 5이다.

 

문제에 대한 아이디어 

공통의 부분 문자열을 찾는 알고리즘이다. 이 알고리즘 가장 유명한 것은 LCS 알고리즘이다. 

LCS는 주로 최장 공통 부분수열을 말한다.  최장 공통 문자열을 말하기도 한다.

최장 공통 부분수열이 최장 공통 문자열 보다 찾기가 어렵다. 

출처 : 그림으로 알아보는 LCS 알고리즘

이 문제는 이중 최장 공통 문자열을 찾는 문제이다.

 

다이나믹 프로그래밍을 이용하여 문제풀기

1. 2차원 배열 만들기

2개의 문자열 길이 만큼 2차원 배열을 생성한다.

 

2. 점화식을 사용하여 문제 풀어나가기

 

G가 있는 첫번째 행부터 생각해보자. G와 A를 비교해보면 같은 것이 없다. 그러므로 0 이다.

G와 B를 비교해도 같은 것이 없다.  G와 B를 비교하는 것은 생각해보면 G와 AB를 비교하는 것이다. 이렇게 모든 행과 열을 비교한다.

이제 2번째 행을 보면 B와 A를 비교하면 0, B와 B는 같기 때문에 1로 해야한다. 하지만 그전에 대각선 왼쪽 위의 값을 확인해야한다. 

이 부분을 알아보기 위해 3번 째 행에 C와 C를 비교한 부분을 보겠다. 둘은 같으므로 +1을 해야한다. 대각선 왼쪽 위를 보면 AB와 GB를 비교한 부분이다. AB와 GB의 비교는 같은 부분 문자열이 B가 1개 존재한다. 그러므로 GBC와 ABC 비교하는 부분은 AB와 GB를 비교한 것 + 1을 해주는 것이다.

• D[ i ][ j ] = D[ i + 1 ][ j + 1 ] + 1인 것이다.

for(int i = 0; i< str1.length(); ++i){
    for(int j = 0; j<str2.length(); ++j){
        if(str1.charAt(i) == str2.charAt(j)){
            pro[i+1][j+1] = pro[i][j] + 1;
            max = Math.max(max, pro[i+1][j+1]);
        }
    }
}

 

최장 공통 부분수열은 어떻게 구할까?

1. 문자열A, 문자열B의 한글자씩 비교하기
2. 두 문자가 다르면 D[ i -1 ][ j ] 와 D[ i ][ j - 1 ] 중 큰 값을 가져온다.
3. 두 문자가 같다면 D[ i - 1][ j - 1 ] 값의 + 1 
4. 이 행동을 반복한다.

 

2번을 왜하냐면 부분수열은 연속된 값이 아니기 때문이다. 

색칠된 부분은 보면 저기는 GBC와 AB를 비교하는 것이다. 공통 부분 문자열은 같은 연속된 것이 없었지만 공통 부분 수열은 공통된 값인 B가 존재한다. 그래서 저번 비교할 때 공통 수열이 존재하면 계속 값을 가져가는 것이다!!

for(int i = 0; i< str1.length(); ++i){
    for(int j = 0; j<str2.length(); ++j){
        if(str1.charAt(i) == str2.charAt(j)){
            pro[i+1][j+1] = pro[i][j] + 1;
        }else{
            pro[i+1][j+1] = Math.max(pro[i][j+1], pro[i+1][j]);
        }
        max = Math.max(max, pro[i+1][j+1]);
    }
}

최장 공통 부분 수열이 어떤 것인지 찾는 방법도 있다.

 

구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 백준_5582 {
    public static void main(String []args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str1 = br.readLine();
        String str2 = br.readLine();
        int [][] pro = new int[str1.length()+1][str2.length()+1];
        int max = 0;
        for(int i = 0; i< str1.length(); ++i){
            for(int j = 0; j<str2.length(); ++j){
                if(str1.charAt(i) == str2.charAt(j)){
                    pro[i+1][j+1] = pro[i][j] + 1;
                }else{
                    pro[i+1][j+1] = Math.max(pro[i][j+1], pro[i+1][j]);
                }
                max = Math.max(max, pro[i+1][j+1]);
            }
        }
        System.out.println(max);
    }
}

https://github.com/Heron-Woong/CodingTest_Practice/commit/bc08bf0deb16b3028dadf79eea21ef8bd9cd30d5

백준_5582, 공통 부분 문자열 · Heron-Woong/CodingTest_Practice@bc08bf0

 

문자열과 관련된 알고리즘!!
1. KMP 알고리즘 : 2개의 문자열이 주어지면 하나의 문자열에 다른 문자열이 존재하는지 검사한다.
2. Boyer-Moore 알고리즘 
3. 편집거리 알고리즘
4. LCS