Pagini recente » Cod sursa (job #202972) | Istoria paginii utilizator/ionuta23 | Rating Radu Iancu (radu.iancu) | Profil blon_dy_nna | Cod sursa (job #2005976)
#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);
scanf("%s", s);
for(int i = 0; i <= strlen(s) ; ++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;
}