공통 부분 문자열(DP)

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

5582번: 공통 부분 문자열

 

문제 이름 그대로 Longest Common Substring의 길이를 찾는 문제

 

LCS에 대하여 정리해놓은 글이 있다

https://djgameprogramming.tistory.com/110

Longest Common Subsequence/Substring(LCS)

 

1. 이중 배열 DP를 생성하고 받은 문자열의 길이만큼 이중 반복문을 돌린다.

2. subject와 target에 대하여 각각 i번째와 j번째 문자가 같을때 DP[i][j]의 값은 DP[i-1][j-1]에서 1을 더해준 값이다.

3. 2번의 과정에서 여태까지 저장한 LCS의 길이보다 큰 값이 나왔다면 갱신해준다.

4. subject와 target에 대하여 각각 i번째와 j번째 문자가 다르다면 DP[i][j]를 0으로 초기화한다.

 

저장한 LCS의 길이를 출력해주면 된다.

 

#include <iostream>
using namespace std;

int DP[4001][4001] = { 0, };
int ret = 0;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	string str1;
	string str2;
	cin >> str1 >> str2;

	int size1 = str1.length();
	int size2 = str2.length();

	for (int i = 1; i <= size1; i++)
	{
		for (int j = 1; j <= size2; j++)
		{
			if (str1[i-1] == str2[j-1])
			{
				DP[i][j] = DP[i - 1][j - 1] + 1;
				ret = max(ret, DP[i][j]);
			}
		}
	}

	cout << ret;
}