[백준] 공통 부분 문자열 (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 이하이다.

출력

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

예제 입력 1 복사

ABRACADABRA ECADADABRBCRDARA

예제 출력 1 복사

5

---

dp 문제이다.

연속으로 공통된 부분 문자열을 찾는 것이기 때문에 LCS 보다 쉬운 문제이다.

단순히 두 문자열에서 최대 몇 글자가 연속으로 공통되는지를 찾으면 된다.

점화식은 다음과 같다.

dp[i][j] = dp[i-1][j-1] + 1 (if A[i] == B[j])

위의 식대로 구현만 하면 된다.

 

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EA%B3%B5%ED%86%B5%20%EB%B6%80%EB%B6%84%20%EB%AC%B8%EC%9E%90%EC%97%B4%20(5582%EB%B2%88).cpp

 

C++ 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int dp[4001][4001];
string A, B;

int main()
{
	cin >> A >> B;
	dp[0][0] = 0;
	int res = 0;
	for (int i = 0; i < A.size(); i++) {
		for (int j = 0; j < B.size(); j++){
			if (A[i] == B[j]) {
				if (i == 0 || j == 0)
					dp[i][j] = 1;
				else
					dp[i][j] = dp[i - 1][j - 1] + 1;
				res = max(res, dp[i][j]);
			}
		}
	}
	cout << res;
}