Pagini recente » Cod sursa (job #421476) | Cod sursa (job #2452576) | Cod sursa (job #2467071) | Cod sursa (job #111674) | Cod sursa (job #570767)
Cod sursa(job #570767)
#include <stdio.h>
#include <string.h>
#define Nmax 2000010
char x[Nmax];
char v[Nmax];
int l[Nmax];
int i,n;
int main()
{
freopen("pscpld.in","r",stdin);
freopen("pscpld.out","w",stdout);
fgets(x,Nmax,stdin);
n = 1;
v[1] = '*';
for (int i = 0; x[i] >= 'a' && x[i] <= 'z'; ++i) {
v[++n] = x[i];
v[++n] = '*';
}
int st=1, dr=3;
l[2] = 1;
for (int i = 3; i <= n; ++i) {
if (i<=dr) {
int poz = dr-i;
if (i + l[st+poz] >= dr) {
l[i] = dr-i;
st = i - l[i];
dr = i + l[i];
while (v[st-1] == v[dr+1] && st > 1) {
--st;
++dr;
++l[i];
}
}
else
l[i] = l[st+poz];
}
else{
l[i] = 0;
st = i;
dr = i;
while (v[st-1] == v[dr+1] && st > 1) {
--st;
++dr;
++l[i];
}
}
}
int ans = 0;
for (i=1; i<=n; ++i)
ans += (l[i]+1)/2;
printf("%d\n", ans);
return 0;
}