[백준] 5582번 공통 부분 문자열

5582번: 공통 부분 문자열

LCS(Longest Common Substring) 문제이다.

문자열 A, B에서

A[i]와 B[j]가 같을 때,

DP[i][j] = DP[i-1][j-1] + 1

이 된다.

 

무슨 말이냐 하면

문자열 A는 ABCDE이고 B는 CDEGG라 할 때

예를 들어

A[4]과 B[2]가 E로 같으면

그 전까지의 문자열 ABCD와 CD에서

가장 길었던 문자열의 길이(DP[3][1])에

E 길이 1을 더한 값이 DP[4][2]에 들어가게 된다.

 

DP 배열의 값 중 가장 큰 값을 출력해주면 된다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string a, b;
int Max, dp[4002][4002];
int main() {
	cin >> a >> b;
	for (int i = 0; i < a.size(); i++) {
		for (int j = 0; j < b.size(); j++) {
			if (a[i] == b[j]) {
				dp[i + 1][j + 1] = dp[i][j] + 1;
				Max = max(Max, dp[i + 1][j + 1]);
			}
		}
	}
	cout << Max;
	return 0;
}