Cod sursa(job #928800)
| Utilizator | Data | 26 martie 2013 18:22:04 | |
|---|---|---|---|
| Problema | PScPld | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.69 kb |
#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;
}
