提出 #72799113

---

ソースコード 拡げる

#include <stdio.h>
#include <string.h>

/*
typedef unsigned long long ull;

ull mulmod(ull a, ull b, ull m) {
	return (ull)((__int128)a * b % m);
}

#define MOD_BY1 435305701817727911ULL
#define MULT1 288896401212481991ULL
#define MULT_INV1 144381709777699389ULL
#define MOD_BY2 895292565250083751ULL
#define MULT2 540720408979433993ULL
#define MULT_INV2 701011253349988479ULL
*/

char str1[4096];
char str2[4096];

short dp[4096][4096];

int main(void) {
	int len1, len2;
	int i, j, ans = 0;
	if (scanf("%4094s", str1 + 1) != 1) return 1;
	if (scanf("%4094s", str2 + 1) != 1) return 1;
	len1 = (int)strlen(str1 + 1);
	len2 = (int)strlen(str2 + 1);
	for (i = 1; i <= len1; i++) {
		for (j = 1; j <= len2; j++) {
			if (str1[i] == str2[j]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
				if (dp[i][j] > ans) ans = dp[i][j];
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

/*

全ての部分文字列のハッシュを用意し、突き合わせる
→ 今回はメモリ制限が厳しいので、厳しそう (最大約16M要素 → 1要素あたり約4B)

チェックする長さを決め打ち
→ ハッシュを用意して突き合わせる
→ ありますか？→二分探索

…でもいいかもだけど、DNAのアライメントのDP的なことをすればよさそう

*/

提出情報

ジャッジ結果