Pagini recente » Cod sursa (job #1011449) | Cod sursa (job #1150067) | Cod sursa (job #199639) | Cod sursa (job #147525) | Cod sursa (job #2791244)
#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], c;
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
s[n++] = '#';
while(scanf("%c", &c) != -1) {
if(!isalpha(c)) break;
s[n++] = c;
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];
}
int anstot = 0;
for(int i = 0; i < n; ++i)
anstot += ans[i] / 2 + ans[i] % 2;
printf("%d", anstot);
return 0;
}