백준 5582 - 공통 부분 문자열

문제 설명

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 두 문자열의 최장 공통 부분 문자열을 구하면 된다.

 

두 문자열의 시작점을 정하고 모두 비교하여 구하게 된다면 시간 초과가 발생할 것이다.

이를 해결하기 위해 DP를 사용하면 된다.

DP에서 관리할 것은 (i, j)에서 최장 공통 부분 문자열의 길이이다.

예를 들어, 두 문자열이 다음과 같다고 가정해 보자.

ABRACADABRA
ECADADABRBCRDARA

i = 5, j = 2라고 한다면 두 문자는 'A'로 동일하다. 

이때, 두 문자열의 최장 공통 부분 문자열의 길이는 1이다.

나아가 i = 6, j = 3이라고 한다면 두 문자는 'D'로 동일하다.

그럼, 두 문자열의 최장 공통 문자열의 길이는 2이다. 이전의 'A'로 공통 부분 문자열이 존재하기 때문이다.

여기서 인덱스를 살펴보면, i, j 모두 1씩 증가했다.

즉, i, j의 문자가 동일하다면 i-1, j-1의 최장 공통 부분 문자열의 길이에 1을 더하는 것과 같다.

이를 코드로 정리하면 다음과 같다.

 

if(str1[i] == str2[j]) dp[i][j] = dp[i-1][j-1] + 1;

이를 모든 i, j에 대해 진행하며 최댓값을 갱신하면 된다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

string str1, str2;

int main() 
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout << fixed;

	cin >> str1 >> str2;

	vector<vector<int>> dp(str1.size(), vector<int>(str2.size(), 0));

	int ans = 0;

	for (int i = 0; i < str1.size(); i++)
	{
		dp[i][0] = str1[i] == str2[0] ? 1 : 0;
	}

	for (int i = 0; i < str2.size(); i++)
	{
		dp[0][i] = str1[0] == str2[i] ? 1 : 0;
	}

	for (int i = 1; i < str1.size(); i++)
	{
		for (int j = 1; j < str2.size(); j++)
		{
			if (str1[i] == str2[j])
			{
				dp[i][j] = dp[i - 1][j - 1] + 1;
				ans = max(ans, dp[i][j]);
			}
		}
	}

	cout << ans;

	return 0;
}

---