[C++, PYTHON] BOJ, 백준 5582 - 공통 부분 문자열

문제 링크

5582번: 공통 부분 문자열

문제 풀이

이 문제는 두 문자열 사이에 공통적으로 존재하는 부분 문자열 중, 가장 길이가 긴 문자열을 찾는 문제이다.

이 문제를 풀기 위해서는 LCS 알고리즘을 사용해야 한다.

LCS 알고리즘

이 알고리즘은 길이가 가장 긴 부분 문자열을 문자열1의 길이 * 문자열2의 길이 만큼의 시간복잡도로 찾을 수 있다.
문자열1의 i번째 문자와 문자열2의 j번째 문자가 같다면, 문자열1의 i-1번째 문자와 문자열2의 j-1번째 문자 배열의 결과에 1을 더해주는 방식으로 문제를 해결할 수 있다.

예를 들어, 문자열 1이 AAAAA고 문자열 2는 BAAAB라고 하자. 그렇다면 가장 긴 부분 문자열은 AAA가 될 것이다. 이것을 LCS로 찾아보도록 하자.

먼저, 문자열 1과 문자열 2에 대한 2차원 배열을 만들어준다.

	0	A	A	A	A	A
0	0	0	0	0	0	0
B	0	0	0	0	0	0
A	0	0	0	0	0	0
A	0	0	0	0	0	0
A	0	0	0	0	0	0
B	0	0	0	0	0	0

위와 같은 형태의 초기 배열을 만들 수 있다. 0행 0열을 넣는 이유는 out of bound를 방지하기 위함이다.

그런다음, 행과 열의 문자들을 비교해서 같은 문자가 나왔을 경우 1을 더해준다.

1행은 B와 AAAAA로 같은 문자가 아니므로 0이 유지된다.

2행은 A와 AAAAA로 모두 같은 문자이므로 1을 더해준다.

	0	A	A	A	A	A
0	0	0	0	0	0	0
B	0	0	0	0	0	0
A	0	1	1	1	1	1
A	0	0	0	0	0	0
A	0	0	0	0	0	0
B	0	0	0	0	0	0

3행도 A와 AAAAA로 모두 같은 문자이므로 1을 더해준다. 이 때, [i,j]가 같다면 [i-1, j-1]번째의 값에 1을 더해주는것이므로 항상 대각선 값에 1을 더해준다.

	0	A	A	A	A	A
0	0	0	0	0	0	0
B	0	0	0	0	0	0
A	0	1	1	1	1	1
A	0	1	2	2	2	2
A	0	0	0	0	0	0
B	0	0	0	0	0	0

4행도 마찬가지로 계산해준다.

	0	A	A	A	A	A
0	0	0	0	0	0	0
B	0	0	0	0	0	0
A	0	1	1	1	1	1
A	0	1	2	2	2	2
A	0	1	2	3	3	3
B	0	0	0	0	0	0

5행은 B와 AAAAA이므로 0이 유지된다.

이런식으로 AAAAA와 BAAAB 사이의 가장 긴 부분 문자열인 AAA의 길이 3이 배열에 나타나게 된다. 배열을 계산하면서, 배열의 값이 초기에 설정해놓은 값보다 크다면, 배열의 값을 초기값 대신 저장하는 방식으로 답을 구해주면 된다.

정답 코드

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

#define fast ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0)
#define ll long long

int LCS[4001][4001];

int main() {
    fast;
    string str1, str2, tmp;
    cin >> str1 >> str2;
    int answer = 0;
    for (int i = 1; i <= str1.length(); i++) {
        for (int j = 1; j <= str2.length(); j++) {
            if (str1[i - 1] == str2[j - 1])
                LCS[i][j] = LCS[i - 1][j - 1] + 1;
            if (LCS[i][j] > answer) answer = LCS[i][j];
        }
    }
    cout << answer;
    return 0;
}

python

str1 = input()
str2 = input()
lcs = [[0] * 4001 for _ in range(4001)]
ans = 0
for i in range(1, len(str1) + 1) :
    for j in range(1, len(str2) + 1) :
        if str1[i - 1] == str2[j - 1] :
            lcs[i][j] = lcs[i - 1][j - 1] + 1
        if lcs[i][j] > ans :
            ans = lcs[i][j]
print(ans)

처음 풀었을 때는, 부분 문자열을 substr로 만들어서 find로 찾아주는 방식을 사용했었는데, 시간초과가 떴다. 아무래도 substr을 한 뒤 find를 하는게, 문자열 전체를 탐색하는것을 무수히 반복하다 보니까 시간이 오래 걸리는듯 했다.