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

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

5582번: 공통 부분 문자열

dp문제였습니다.

 

 

풀이방법

 d[i][j] =  i부분과 j부분의 문자가 같다면 그 이전의 최대길이 + 1 로 정의합니다.

 

 

Code

#include <bits/stdc++.h>
using namespace std;
string s, t;
int ans, d[4001][4001];
int main(){
    cin >> s >> t;
    for(int i = 0; i < s.size(); i++){
        for(int j = 0; j < t.size(); j++){
            if(s[i] == t[j]){
                d[i+1][j+1] = d[i][j] + 1;
                ans = max(ans,d[i+1][j+1]);
            }
        }
    }
    cout << ans << '\n';
}

 

Test Case

질문 게시판에 있는 반례들입니다.

 

입력:
PORPOISE
PROPORTION

정답:
3

입력:
ACMICPC
ACMICPCNET

정답:
7