전공/알고리즘
백준 5582(공통 부분 문자열)
xkdlaldfjtnl
2020. 11. 16. 15:39
5582번: 공통 부분 문자열
두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들
www.acmicpc.net
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;
}