Pagini recente » Cod sursa (job #2450607) | Cod sursa (job #2309672) | Cod sursa (job #2089614) | Cod sursa (job #246734) | Cod sursa (job #928800)
Cod sursa(job #928800)
#include<stdio.h>
#include<string.h>
char s[1000005];
char t[2000005];
int p[2000005];
int min(int a,int b)
{
return a<b?a:b;
}
int main()
{
FILE *f,*g;
f=fopen("pscpld.in","r");
g=fopen("pscpld.out","w");
fgets(s,1000005,f);
t[0]='+';int u=0;
long long ans=0;
for(int i=0;s[i]!='\n';i++)
t[++u]='#',t[++u]=s[i];
t[++u]='#';
t[++u]='-';
//fputs(t,stderr);
//fprintf(stderr,"\n");
int C,L; C=L=0;
for(int i=1;i<u-1;i++)
{
int j=2*C-i;
//fprintf(stderr,"C=%d L=%d ",C,L);
p[i]=(L>i)?min(L-i,p[j]):0;
while(t[i+p[i]+1]==t[i-p[i]-1])
p[i]++;
if(i+p[i]>L)
C=i,
L=i+p[i];
//fprintf(stderr,"%d\n",p[i]);
ans=ans+(p[i]+1)/2;
}
fprintf(g,"%lld\n",ans);
return 0;
}