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

www.acmicpc.net/problem/5582

5582번: 공통 부분 문자열

LCS 공통 부분 수열과는 다른 문제이다. 

 

subsequence 는 부분 수열로 수열에서 그냥 임의의 갯수를 삭제해서 만들고, 

substring 은 부분 문자열로 문자열의 처음과, 끝에서 인접한 임의의 갯수를 삭제할 수 있다. 

 

이건 n^2 dp로 구할 수 있는데, 만약에 같으면 그냥 +1을 해주면 된다. 

 

그리고 다른 경우 바로 초기화를 해준다. 

 

모든 계산 가능한 구간에 대해서 알아보는 n^2이다. 

 

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

int lcs[4003][4003];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	string a, b;
	cin >> a >> b;
	a = '0' + a;
	b = '0' + b;
	int len1 = a.size();
	int len2 = b.size();
	int ans=0;
	for (int i = 0; i < len1; i++) {
		for (int j = 0; j < len2; j++) {
			if (i == 0 || j == 0) {
				lcs[i][j] = 0;
				continue;
			}
			if (a[i] == b[j]) {
				lcs[i][j] = lcs[i - 1][j - 1] + 1;
				ans = max(ans, lcs[i][j]);
			}
		}
	}
	cout << ans;
}