백준 5582(공통 부분 문자열)

문제

5582번: 공통 부분 문자열

두개의 문자열이 주어지면 공통 부분 문자열이 가장 긴 길이를 출력하면 되는 문제입니다.

예를 들어

ABRACADABRA
ECADADABRBCRDARA

두개의 문자열이 주어지면 가장 긴 공통 부분 문자열은 

ABRACADABRA
ECADADABRBCRDARA

이므로 5를 출력해주면 됩니다.

해당 문제는 최장 공통 부분 수열(Longest Common Subsequence)문제입니다.

하지만 다른 점은 기본적인 lcs는 굳이 문자열이 연속 되지 않아도 되었지만, 

해당 문제는 무조건 공통 부분 문자열이 연속되어야 하는 것입니다.

따라서 lcs알고리즘을 수정할 필요가 있습니다.

int a = s1.length();
int b = s2.length();

int ans = 0;
for (int i = 1; i <= a; i++) {
	for (int j = 1; j <= b; j++) {
		if (s1[i - 1] == s2[j - 1]) {
			dp[i][j] = dp[i - 1][j - 1] + 1;
			ans = max(ans, dp[i][j]);
		}
	}
}
cout << ans;

어차피 연속된 공통 수열을 찾기 때문에 틀린 부분이 있으면 0으로 넣어주고, 만약 같다면 lcs알고리즘과 같습니다.

표를 보시면 금방 이해가 갈것입니다.

---

전체 코드입니다.

#include<iostream>
#include<string>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>

#define INF 2000000000
using namespace std;
using ll = long long;
int dp[4001][4001];
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	string s1;
	cin >> s1;
	string s2;
	cin >> s2;

	int a = s1.length();
	int b = s2.length();

	int ans = 0;
	for (int i = 1; i <= a; i++) {
		for (int j = 1; j <= b; j++) {
			if (s1[i - 1] == s2[j - 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
				ans = max(ans, dp[i][j]);
			}
		}
	}
	cout << ans;


	return 0;
}