[BOJ / C++] 5582번 : 공통 부분 문자열

문제

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

어떤 문자열 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 이하이다.

출력

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

Solved.ac 레벨

골드 V

풀이

LCS (Longest Common Subsequence, 최장 공통 부분 수열) 문제였다.

지난 번에 풀었던 9251번 : LCS 문제와 비슷하나 9251번 문제에서는 반드시 이어지지 않아도 된다는 고려 사항이 있었지만, 이번 문제는 끊어지지 않고 이어지는 LCS를 구하는 문제다.

 

주어진 예제들이 너무 길어 표로 나타내기가 번거롭기 때문에 간단히 ABBA, BBAC 두 문자열의 LCS를 구하는 과정을 통해 풀이를 해보자.

 

dp배열은 문자열 A의 길이 * 문자열 B의 길이로 선언하였고, 0으로 초기화하였다.

 

B / A	0	A	B	B	A
0	0	0	0	0	0
B	0	0	0	0	0
B	0	0	0	0	0
A	0	0	0	0	0
C	0	0	0	0	0

 이제부터 문자열 B를 문자열 A의 0 ~ i 까지와 비교하며 LCS의 길이를 저장해나간다.

 

1. A[0]일 때 ('A')

B / A	0	A	B	B	A
0	0	0	0	0	0
B	0	0	0	0	0
B	0	0	0	0	0
A	0	1	0	0	0
C	0	0	0	0	0

B[2]가 비교 대상인 A와 같으므로 왼쪽 대각선 칸 + 1하여 LCS의 길이를 증가시킨다.

 

2. A[1]일 때 ('B')

B / A	0	A	B	B	A
0	0	0	0	0	0
B	0	0	1	0	0
B	0	0	1	0	0
A	0	1	0	0	0
C	0	0	0	0	0

B[0], B[1]가 비교 대상인 B와 같으므로 왼쪽 대각선 칸 + 1하여 LCS의 길이를 증가시킨다.

 

3. A[2]일 때 ('B')

B / A	0	A	B	B	A
0	0	0	0	0	0
B	0	0	1	1	0
B	0	0	1	2	0
A	0	1	0	0	0
C	0	0	0	0	0

B[0], B[1]가 비교 대상인 B와 같으므로 왼쪽 대각선 칸 + 1하여 LCS의 길이를 증가시킨다.

 

4. A[3]일 때 ('A')

B / A	0	A	B	B	A
0	0	0	0	0	0
B	0	0	1	1	0
B	0	0	1	2	0
A	0	1	0	0	3
C	0	0	0	0	0

B[2]가 비교 대상인 A와 같으므로 왼쪽 대각선 칸 + 1하여 LCS의 길이를 증가시킨다.

이렇게 해서 ABBA와 BBAC의 LCS는 BBA이며 길이는 3이 된다.

 

왼쪽 대각선 위 칸 + 1을 이용해 점화식을 작성해보면 아래와 같다.

if(A[i] == B[j]) dp[i][j] += dp[i - 1][j - 1] + 1

 dp[i][j]를 저장한 후 최댓값을 갱신하여 최장길이를 구한다.

Code

#include<bits/stdc++.h>

using namespace std;

string a, b;
int dp[4001][4001];
int ans = 0;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> a >> b;

    for(int i = 1; i <= a.length(); i++) {
        for(int j = 1; j <= b.length(); j++) {
            if(a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }

            ans = max(ans, dp[i][j]);
        }
    }

    cout << ans << "\n";

    return 0;
}

 

5582번: 공통 부분 문자열