Cod sursa(job #230435)
Utilizator | Data | 13 decembrie 2008 22:04:58 | |
---|---|---|---|
Problema | PScPld | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.45 kb |
#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;
}