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

문제보기 : 백준 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 예제 출력  5

문제 분석

---

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

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

Input
GeeksforGeeks
GeeksQuiz
Output
5

Input
abcdxyz
xyzabcd
Output
4

Input
zxabcdezy
yzabcdezx
Output
6

위와 같은 경우를 최장 공통 부분 문자열(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 공식은 다음과 같다.

소스코드

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

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