[ boj : 3793 ] Common Subsequence

www.acmicpc.net/problem/3793

3793번: Common Subsequence

문제 : 두개의 문자열이 주어지고 서로 부분 공통 문자열의 최대 길이를 구하시오.

 

해설 : 그냥 전형적인 LCS(Longest Common Subsequence) 문제입니다.

i번째 문자와 j 번째 문자가 같다면 (i-1,j-1) 의 값에서 +1 해주면 되고 아니라면 MAX[(i-1,j),(i,j-1)]을 해주면 됩니다.

 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

string x, y;
ll dp[201][201];

void solve();

int main()
{
	
	while (true) {
		cin >> x >> y;
		if (cin.eof()==true)break;
		memset(dp, 0, sizeof(dp));
		solve();
	}
}
void solve()
{
	for (int i = 0; i < x.length(); i++) {
		for (int j = 0; j < y.length(); j++)
		{
			if (y[j] == x[i])
				dp[i + 1][j + 1] = dp[i][j] + 1;
			else
				dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
		}
	}
	cout << dp[x.length()][y.length()]<<"\n";
}