Pagini recente » Cod sursa (job #785815) | Cod sursa (job #438202) | Cod sursa (job #26459) | Cod sursa (job #214016) | Cod sursa (job #2791250)
#include <iostream>
#include <cstring>
using namespace std;
const int NMAX = 1000000;
int n, ans[2 * NMAX + 3], centru = 1, raza;
char s[2 * NMAX + 3], inp[NMAX + 3], c;
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
scanf("%s", inp);
s[n++] = '#';
for(int i = 0; inp[i]; ++i) {
s[n++] = inp[i];
s[n++] = '#';
}
for(int i = 1; i < n; ++i) {
const int simi = 2 * centru - i;
if(i <= raza)
ans[i] = min(raza - i, ans[simi]);
while(i + 1 + ans[i] < n && i - 1 - ans[i] >= 0 && s[i + 1 + ans[i]] == s[i - 1 - ans[i]])
++ans[i];
if(i + ans[i] > raza)
centru = i, raza = i + ans[i];
}
long long anstot = 0;
for(int i = 0; i < n; ++i)
anstot += 1ll * ans[i] / 2 + ans[i] % 2;
printf("%lld", anstot);
return 0;
}