問題
解法
動的計画法が使える。
詳しくはソースで
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_STRLEN = 4001;
int len1, len2;
char str1[MAX_STRLEN];
char str2[MAX_STRLEN];
int dp[MAX_STRLEN][MAX_STRLEN];
int solve(){
int ans = 0;
for(int i = 0; i < len1; i++){
for(int j = 0; j < len2; j++){
if(str1[i] == str2[j]){
dp[i + 1][j + 1] = dp[i][j] + 1;
ans = max(ans, dp[i + 1][j + 1]);
}
}
}
return ans;
}
int main(){
char c;
while(scanf("%s", str1) != EOF){
scanf("%c", &c);
scanf("%s", str2);
scanf("%c", &c);
len1 = strlen(str1);
len2 = strlen(str2);
for(int i = 0; i <= len1; i++){
for(int j = 0; j <= len2; j++){
dp[i][j] = 0;
}
}
printf("%d\n", solve());
}
return 0;
}