PALINY - Palindrome dài nhất
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
using namespace std;
int MOD = 7999993;
int COSO = 241;
int n;
char a[120000];
int total[120000], pow[120000];
int POW(int a, int sm) {
if(sm==0) return 1;
int r = POW(a,sm/2);
if(sm%2) return r * 1LL * r % MOD * a % MOD;
else return r * 1LL * r % MOD;
}
int calc(int i, int j) {
return (MOD + total[j] - (i==0 ? 0 : total[i-1])) % MOD * 1LL * pow[i] % MOD;
}
int main() {
scanf("%d", &n);
gets(a);
gets(a);
memmove( a + n, a, n);
reverse( a, a + n);
for(int i=0,z=1;i<2*n;++i,z = ( z * COSO ) % MOD)
total[i] = ((i==0 ? 0 : total[i-1]) + z * a[i]) % MOD;
for(int i=0,z=POW(COSO,MOD-2);i<2*n;++i)
pow[i] = (i==0 ? 1 : (pow[i-1] * 1LL * z % MOD));
int res = 0, result = 0;
for(int i=(1<<15);i>=1; i/=2) if((res+i)*2 <= n) {
bool ok = false;
for(int j=0;j+2*(res+i)<=n;++j)
if(calc(j,j+2*(res+i)-1) == calc(2*n-j-2*(res+i),2*n-j-1)) {
ok = true;
break;
}
if(ok) res += i;
}
result >?= res * 2;
res = 0;
for(int i=(1<<15);i>=1; i/=2) if((res+i)*2-1 <= n) {
bool ok = false;
for(int j=0;j+2*(res+i)-1<=n;++j)
if(calc(j,j+2*(res+i)-1-1) == calc(2*n-j-2*(res+i)+1,2*n-j-1)) {
ok = true;
break;
}
if(ok) res += i;
}
result >?= res * 2 - 1;
cout << result << endl;
// system("pause");
return 0;
}