NKLETTER - Gửi thư

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<cstring>

#define N 255 
#define MOD 1000000007LL
typedef long long LL;

char a[N], b[N];
int n, m;
LL hashA[N], pow[N], hashB[N];

void init() {
	hashA[0] = 0; hashB[0] = 0; pow[0] = 1;
	for(int i = 1; i <= n; ++i) hashA[i] = (hashA[i-1] * 26 + a[i] - 'a') % MOD;
	for(int i = 1; i <= m; ++i) hashB[i] = (hashB[i-1] * 26 + b[i] - 'a') % MOD;
	for(int i = 1, _n = n > m ? n : m; i <= _n; ++i) pow[i] = (pow[i-1] * 26) % MOD;
}

inline LL getHashA(int i, int j) {
	return (hashA[j] - hashA[i-1] * pow[j-i+1] + MOD * MOD) % MOD;
}

inline LL getHashB(int i, int j) {
	return (hashB[j] - hashB[i-1] * pow[j-i+1] + MOD * MOD) % MOD;
}

int main() {
	scanf("%s%s", a+1, b+1); n = strlen(a+1); m = strlen(b+1);
	init();
	for(int i = n>=m ? n-m+1 : 1, j = n>=m ? m : n; i<=n&&j>0; ++i, --j) {
		if(getHashA(i, n) == getHashB(1, j)) {
			printf("%d\n", n + m - j);
			return 0;
		}
	}
	printf("%d\n", n+m);
	return 0;
}

Download