Pagini recente » Cod sursa (job #45254) | Cod sursa (job #2266990) | Cod sursa (job #596243) | Cod sursa (job #1784316) | Cod sursa (job #230428)
Cod sursa(job #230428)
#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] = 3;
for (int i=3;i<=n;++i)
{
if (i<=dr)
{
int poz = i-st;
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 > 0)
{
--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 > 0)
{
--st;
++dr;
++l[i];
}
}
}
int ret = 0;
for (int i=2;i<=n;++i)
if (v[i] == ' ') ret += (l[i]+1)/2;
else ret += 1 + (l[i]/2);
printf("%d\n",ret);
return 0;
}