백준 BOJ 5582 - 공통 부분 문자열

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

5582번: 공통 부분 문자열

DP로 해결했습니다.

 

dp[i][j] 를

문자열 A를 i번 인덱스까지 자르고,

문자열 B를 j번 인덱스까지 잘랐을 때

두 문자열의 공통 접미사의 길이 로 정의한다.

 

이제 이 dp 배열을 O(N^2) 로 순회하면서 채우는데,

만일 A[i] 와 B[i]가 서로 같다면

A[i-1]과 B[i-1] 도 서로 비교해 보아야 한다.

 

이때, dp[i-1][j-1] 이

공통 접미사의 길이를 이미 저장하고 있기 때문에,

이 dp[i-1][j-1] 의 값에 1을 더해서 dp[i][j]에 저장해주면 된다.

 

즉, dp[i-1][j-1]이 0이라면, 두 문자열 A'와 B'는 마지막 인덱스에서만

서로 같은 문자열인 것이기 때문에,

dp[i][j] 를 1로 설정해 주고,

 

만일 dp[i-1][j-1]이 어떠한 수 k라면, 두 문자열 A'와 B'는

이미 뒤에서부터 K자리가 서로 같은 문자열이면서, A[i]와 B[j] 도 서로 같기 때문에

dp[i][j]를 k+1로 갱신해주면 된다.

 

모든 부분문자열에 대해서 확인해봐야 하기 때문에,

정답은 모든 dp 배열에서의 최댓값을 출력해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;

int dp[4567][4567] = {0};

int main(){
	string A,B;
	cin >> A >> B;
	
	int ans = 0;
	for(int i=0; i<A.length(); i++){
		for(int j=0; j<B.length(); j++){
			if(A[i] == B[j]){
				dp[i+1][j+1] = dp[i][j] + 1;
				ans = max(ans, dp[i+1][j+1]);
			}
		}
	}
	
	cout << ans;
	return 0;
}