백준 5582 - 공통 부분 문자열(C++)

문제 링크입니다. https://www.acmicpc.net/problem/5582

5582번: 공통 부분 문자열

Dp를 이용해 푸는 문제입니다.

주어진 2개의 문자열에서 공통으로 가장 긴 문자열을 찾는 문제입니다.

 

위의 문자열을 X, 아래 문자열을 Y라고 할 때, X문자열의 문자를 1번부터 하나씩 늘려가면서 Y와 비교했습니다.

 

사용된 논리는 LCS와 비슷합니다.

아래를 확인해주세요. https://junseok.tistory.com/170

백준 9251 - LCS(C++)

 

 

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#define INF 987654321

using namespace std;

int dp[4001][4001];
string X, Y;

void solve(){
    int ans = 0;
    for(int i = 1; i <= X.size(); i++){
        for(int j = 1; j <= Y.size(); j++){
            if(X[i-1] == Y[j-1]){
                dp[i][j] = max(1, dp[i-1][j-1] + 1);
                ans = max(ans, dp[i][j]);
            }
        }
    }
    cout << ans;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> X >> Y;
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.