백준 5582번 공통 부분 문자열 - C++ 풀이

---

 

1. dp(p, q) = S[p...]와 T[q...]가 앞에서부터 일치하는 최대 글자 수
2. S[p] = T[q]인 경우 dp(p, q) = 1 + dp(p+1, q+1)이고, 아닌 경우 0이다. 
3. dp(p, q)의 최댓값이 최장 공통부분 문자열의 길이이다.

 

1. dp(p, q) = S[p...]와 T[q...]가 앞에서부터 일치하는 최대 글자 수

 dp(p, q)를 위와 같이 정의하자.

 

2. S[p] = T[q]인 경우 dp(p, q) = 1 + dp(p+1, q+1)이고, 아닌 경우 0이다. 

 S[p] = T[q]인 경우, 그다음 글자를 비교해야 하므로 dp(p, q) = 1 + dp(p+1, q+1)이 된다. dp(p, q)는 "앞에서부터" 일치하는 최대 글자 수이므로, S[p] != T[q]인 경우에는 더 이상 비교할 것도 없이 dp(p, q) = 0이다.

 

2. dp(p, q)의 최댓값이 최장 공통부분 문자열의 길이이다.

모든 매칭 경우를 고려해준 뒤 최대값을 찾으면 된다. 즉, 0 ≤ p ≤ (S의 길이-1), 0 ≤ q ≤ (T의 길이-1)인 모든 p, q쌍에 대해 구한 dp(p, q) 중 최댓값이 최장 공통부분 문자열의 길이가 된다. 

 

반응형

---

#include <iostream>
#include <string.h>

using namespace std;

string S, T;
int cache[4000][4000];

// dp(p, q): S[p...]와 T[q...]가 앞에서부터 몇글자 일치하는지
int dp(int p, int q) {
    if (p >= S.size() || q >= T.size()) return 0;
    
    int& ret = cache[p][q];
    if (ret != -1) return ret;
    
    if (S[p] != T[q]) ret = 0;
    else ret = 1 + dp(p+1, q+1);
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    memset(cache, -1, sizeof(cache));
    
    cin >> S >> T;
    
    int maxLen = 0;
    
    for (int i=0; i<S.size(); i++) {
        for (int j=0; j<T.size(); j++) {
            maxLen = max(maxLen, dp(i, j));
        }
    }
    
    cout << maxLen;

    return 0;
}