Pagini recente » Profil iHateNiggers | Istoria paginii utilizator/cameliagheorghiu | Istoria paginii utilizator/raduapreotesei1 | Istoria paginii utilizator/robyrobt | Cod sursa (job #2005983)
#include <bits/stdc++.h>
using namespace std;
char s[1000005], T[2000005];
int P[2000005];
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
fgets(s, sizeof(s), stdin);
int L = strlen(s) - 1;
for(int i = 0; i < L ; ++i)
T[2 * i] = '#', T[2 * i + 1] = s[i];
int n = strlen(T), C = 0, R = -1, rad, Sol = 0;
for(int i = 0; i < n ; ++i){
if(i <= R) rad = min(P[2 * C - i], R - i) + 1;
else rad = 0;
while(i + rad < n && i - rad >= 0 && T[i - rad] == T[i + rad]) ++rad;
P[i] = rad - 1;
if(i + rad - 1 > R){
C = i;
R = i + rad - 1;
}
Sol = Sol + (P[i] + 1) / 2;
}
printf("%d", Sol);
return 0;
}