Cod sursa(job #75255)

Utilizator Ragnar_LodbrokGrosu Codrut Ragnar_Lodbrok Data 31 iulie 2007 18:29:20
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#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;
}