AOJ_0528 Common Sub-String

問題
解法
動的計画法が使える。
詳しくはソースで

#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;
}