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

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

5582번: 공통 부분 문자열

<코드>

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

int main()
{
	string s1,s2;
	cin>>s1>>s2;
	vector<vector<int>>dp(4001,vector<int>(4001,0));
	int result = 0;
	for(int i=1;i<=s1.size();i++)
	{
		for(int j=1;j<=s2.size();j++){
			if(s1[i-1]==s2[j-1])
			{
				dp[i][j] = dp[i-1][j-1]+1;
				result = max(dp[i][j],result);
			}
		}
	}
	cout<< result<<'\n';
}

<풀이 과정>

이 문제는 LCS(최장공통부분수열)과 비슷한 문제이지만, LCS에서는 ABDCE AEBCE 이런식으로 두 부분을 비교해주면 공통수열은 ACE가 되지만, 공통 부분 문자열에서는 CE만이 부분 문자열이 된다. 즉, LCS랑은 다르게, 끊어지지 않는 공통부분문자열을 찾는 문제이다.

문자가 같을 경우에만 비교해주면 되기 때문에 비교적 해결하기 수월한 문제였다.