Pagini recente » Cod sursa (job #1408409) | Cod sursa (job #2196085) | Cod sursa (job #502820) | Cod sursa (job #199167) | Cod sursa (job #230435)
Cod sursa(job #230435)
#include <stdio.h>
#define Nmax 2000100
int n,l[Nmax];
char x[Nmax/2],v[Nmax];
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] = ' ';
}
//printf("%s\n", v+1);
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];
}
}
}
long long ret = 0;
for (int i=1;i<=n;++i)
if (v[i] == ' ') ret += (l[i]+1)/2;
else ret += 1 + (l[i]/2);
printf("%lld\n",ret);
return 0;
}