Pagini recente » Cod sursa (job #1349442) | Cod sursa (job #2194835) | Cod sursa (job #2144462) | Cod sursa (job #2326672) | Cod sursa (job #75255)
Cod sursa(job #75255)
#include <stdio.h>
#include <string.h>
#define NMAX 2000005
#define MMAX 1000005
FILE *fin,*fout;
typedef long long LL;
char sir[NMAX+1],s[MMAX+1];
int p,radius[NMAX+1],N;
LL S;
int main()
{int i,j;
fin=fopen("pscpld.in","r");
fout=fopen("pscpld.out","w");
fscanf(fin,"%s",s);
fclose(fin);
N=strlen(s);
for (i=0;i<N;++i)
{sir[2*i]=s[i];
sir[2*i+1]='.';
}
N<<=1;
S=1;
radius[0]=0;p=0;
for (i=1;i<N;++i)
{if (p+radius[p]<i)
{for (j=1;i-j>=0&&i+j<N&&sir[i-j]==sir[i+j];++j);
--j;radius[i]=j;
p=i;
}
else
{j=p-(i-p);
radius[i]=radius[j];
if (radius[i]>radius[p]-i+p) radius[i]=radius[p]-i+p;
if (radius[i]+i==p+radius[p])
while (radius[i]+1<=i&&i+radius[i]+1<N&&sir[i-radius[i]-1]==sir[radius[i]+i+1])
++radius[i];
if (p+radius[p]<i+radius[i]) p=i;
}
if (sir[i]=='.') S=S+(radius[i]>>1)+(radius[i]%2);
else S=S+1+(radius[i]>>1);
}
/*printf("%s\n",sir);
for (i=0;i<N;++i) printf("%d ",radius[i]);*/
fprintf(fout,"%lld\n",S);
fclose(fout);
return 0;
}