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

문제

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

---

문제 요약

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열의 길이를 출력한다.

 

예시

문자열 A = "ABRACADABRA"

문자열 B= "ECADADABRBCRDARA"

 

가장 긴 공통 부분 문자열은 "ADABR"이고, 길이는 5이다.

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

// dp[i][j]: 문자열 A에서 i번째 문자, 문자열 B에서 j번째 문자에서 끝나는 가장 긴 공통 부분 문자열 길이
int dp[4040][4040];
string A, B;

int res;

int main() {
    cin >> A >> B;

    for (int i = 1; i <= A.size(); i++) {
        for (int j = 1; j <= B.size(); j++) {
            // 비교하는 두 문자가 다를 경우 0
            if (A[i - 1] != B[j- 1]) continue;

            dp[i][j] = dp[i - 1][j - 1] + 1;

            res = max(res, dp[i][j]);

        }
    }

    cout << res;

    return 0;
}

---

코드 설명

2차원 Dynamic Programming을 이용한다.

 

2차원 배열 dp[i][j]는 문자열 A에서 i번째 문자, 문자열 B에서 j번째 문자에서 끝나는 가장 긴 공통 부분 문자열 길이이다.

 

Bottom - up 방식으로 이중 반복문을 통해 각 문자열의 문자를 하나씩 접근하며 dp 테이블을 채운다.

 

1. 비교하는 두 문자 i, j가 다를 경우, i, j번째 문자에서 끝나는 공통 부분 문자열이 없으므르 0이다.

 

2. 비교하는 두 문자 i, j가 같을 경우, i - 1, j - 1번째 문자에서 끝나는 공통 부분 문자열에서 해당 문자를 붙이면 된다.

 

3. dp[i][j]를 구할 때마다. 최대 값을 갱신한다.

 

4. dp 테이블을 모두 채웠다면, 최대 값을 출력한다.

---

고찰

LCS와 함께 직접 2차원 dp 테이블을 그려보면, 쉽게 이해할 수 있다.