Pagini recente » Cod sursa (job #1224723) | Cod sursa (job #2341812) | Cod sursa (job #1218021) | Cod sursa (job #2615028) | Cod sursa (job #492612)
Cod sursa(job #492612)
#include <stdio.h>
using namespace std;
#define maxn 1000100
int n, i, j, k, st, dr, cmax, drm;
int v[2*maxn];
char s[maxn];
long long sol;
int main()
{
freopen("pscpld.in", "r", stdin);
freopen("pscpld.out", "w", stdout);
scanf("%s", s+1);
n=1;
while(s[n]!=0)
++n;
--n;
cmax=1;
drm=1;
for(int i=1; i<2*n; i+=2)
v[i]=1;
for(int i=1; i<2*n; ++i)
{
if(drm>=i/2+i%2)
v[i]=v[2*cmax-i];
if(i%2)
{
dr=i/2+1+v[i]/2;
st=i/2+1-v[i]/2;
}
else
{
dr=i/2+v[i]/2;
st=i/2-v[i]/2+1;
}
// printf("%d %d\n", st, dr);
if(dr>drm)
{
v[i]-=2*(dr-drm);
st+=dr-drm;
dr=drm;
}
// printf("%d %d\n\n", st, dr);
while(s[st-1]==s[dr+1] && st>1 && dr<n)
{
v[i]+=2;
dr++;
st--;
}
if(dr>drm)
{
cmax=i;
drm=dr;
}
if(i%2)
sol=sol+v[i]/2+1;
else
sol=sol+v[i]/2;
// printf("%d ", v[i]);
}
// printf("\n");
printf("%lld\n", sol);
return 0;
}