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

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

 

문제

---

두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오.

어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다.

두 문자열 ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR, 빈 문자열 등이 있다. 이 중에서 가장 긴 공통 부분 문자열은 ADABR이며, 길이는 5이다. 또, 두 문자열이 UPWJCIRUCAXIIRGL와 SBQNYBSBZDFNEV인 경우에는 가장 긴 공통 부분 문자열은 빈 문자열이다.

 

입력

---

첫째 줄과 둘째 줄에 문자열이 주어진다. 문자열은 대문자로 구성되어 있으며, 길이는 1 이상 4000 이하이다.

 

출력

---

첫째 줄에 두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 출력한다.

 

문제 풀이

---

dp 문제.

M*N 크기의 dp 배열을 만들어 해당 위치에서 가질 수 있는 길이를 저장한다.

만약 둘째 줄 문자열의 i번째 인덱스와 첫째 줄 문자열의 j번째 인덱스의 문자가 같다면 둘째 줄 문자열의 i-1번째 인덱스까지와 첫째 줄 문자열의 j-1번째 인덱스까지 얻어낸 값에 1을 더하면 된다. 따라서 dp[i][j]=dp[i-1][j-1]+1이 성립한다.

만약 같지 않다면 0으로 초기화해준다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
using namespace std;

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

	string str1, str2;
	cin >> str1 >> str2;
	int N = str1.length();
	int M = str2.length();
	int** lengths = new int*[M+1];
	int maxLength = 0;
	for (int i = 0; i < M+1; i++)
	{
		lengths[i] = new int[N+1];
		for (int j = 0; j < N+1; j++)
		{
			lengths[i][j] = 0;
		}
	}
	for (int i = 1; i < M+1; i++)
	{
		for (int j = 1; j < N+1; j++)
		{
			if (str2.at(i - 1) == str1.at(j - 1))
			{
				lengths[i][j] = lengths[i - 1][j - 1] + 1;
				maxLength = max(maxLength, lengths[i][j]);
			}
			else
			{
				lengths[i][j] = 0;
			}
		}
	}
	cout << maxLength << "\n";
	return 0;
}