백준 5582 : 공통 부분 문자열 풀이

개발/Algorithm

백준 5582 : 공통 부분 문자열 풀이

워너-비 2018. 3. 8. 17:36

문제보기 : 백준 5582

한국어원문

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	2565	996	825	44.813%

문제

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.

어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.

두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통 부분 문자열은 빈 문자열이다.

입력

첫째 줄과 둘째 줄에 문자열이 주어진다. 문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.

출력

첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다.

예제 입력

ABRACADABRA
ECADADABRBCRDARA

예제 출력

문제 분석

두 문자열이 주어졌을때, 공통되는 가장 긴 문자열의 길이를 구하는 문제이다.

이해를 돕기위한 예는 다음과 같다.

Input

GeeksforGeeks

GeeksQuiz

Output

Input

abcdxyz

xyzabcd

Output

Input

zxabcdezy

yzabcdezx

Output

위와 같은 경우를 최장 공통 부분 문자열(LCS;Longest Common Substring) 이라 한다.

문제 해결을 위해서 어떤 방법이 있을까?

두 문자열을 str_1, str_2라 하고, 각각의 길이를 m, n이랑 하자.

방법 1

먼저 생각해볼 수 있는 방법은 str_1의 부분집합에 해당하는 모든 부분 문자열들을 두번째 문자열 str_2의 모든 부분 문자열들에 일일이 비교하며 최장 공통 부분 문자열을 찾는 것이다.

str_1에는 O(m^2) 개의 부분 문자열이 있으며, 그것들이 str_2에 포함되는지 여부를 알아보기 위해서는 O(n) 시간이 필요하다.

따라서 시간복잡도는 O(m^2 * n) 이다.

해당 방법은 시간초과가 발생하므로 답안이 될 수 없다.

방법 2

다음 방법은 다이나믹 프로그래밍(Dynamic Programming)을 이용하여 해결하는 것이다.

두 문자열의 모든 부분 문자열에 대해 공통 부분 문자열의 길이를 2차원 배열에 저장해나가는 것이다.

가장 긴 공통 문자열의 길이는 배열의 최대값이 된다.

str_1, str_2의 길이를 각각 m, n이라 할때, 최장 공통 부분 문자열을 찾는 시간복잡도는 O(m*n)가 된다.

LCS 공식은 다음과 같다.

${\mathit {LCSuff}}(S_{{1..p}},T_{{1..q}})={\begin{cases}{\mathit {LCSuff}}(S_{{1..p-1}},T_{{1..q-1}})+1&{\mathrm {if}}\;S[p]=T[q]\\0&{\mathrm {otherwise}}.\end{cases}}$

소스코드

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        
        int dp[][] = new int[4005][4005];
        String str1;
        String str2;
        
        str1 = s.nextLine();
        str2 = s.nextLine();
        int m = str1.length();
        int n = str2.length();
        int answer = 0;
        
        for(int i = 0 ; i < m ; ++i){
            for(int j = 0 ; j < n ; ++j){
                if(str1.charAt(i) == str2.charAt(j)){
                    dp[i+1][j+1] = dp[i][j]+1;
                    answer = Math.max(ans, dp[i+1][j+1]);
                }
            }
        }
        System.out.println(answer);
    }
}

티스토리