알고리즘 문제
[C/C++ 백준 5582번] 공통 부분 문자열 (Gold 5)
새파란 공대생
2020. 10. 19. 20:08
5582번: 공통 부분 문자열
두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들
www.acmicpc.net
오히려 LCS문제보단 더 편한것 같은 문제이다.
1. dp[i][j]를 각 문장의 i번째 문자, j번째 문자를 끝으로하는 공통부분 문자열이라고 하자.
2. 당연히 각 문자가 다르면 dp는 0, 아니라면 dp는 dp[i-1][j-1]+1이 된다.
3. 모든 dp중 최댓값을 출력하자.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main(void){
char s[4001];
char t[4001];
scanf("%s %s", s, t);
int s1 = strlen(s), s2 = strlen(t), maxi = -1;
int dp[s1][s2];
for(int i=0; i<s1; i++){
for(int j=0; j<s2; j++){
if(s[i]==t[j]){
if(i==0 || j==0){
dp[i][j] = 1;
}
else
dp[i][j] = dp[i-1][j-1]+1;
}
else
dp[i][j]=0;
//printf("%d ",dp[i][j]);
maxi = max(dp[i][j], maxi);
}
//printf("\n");
}
printf("%d", maxi);
}