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