Cod sursa(job #123587)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 16 ianuarie 2008 18:11:30
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include<stdio.h>
#include<string.h>
char *s,sir[2000005];
long int L,sol,i,lung[2000005],st,dr,na;
int main()
{
	FILE *f,*g;f=fopen("pscpld.in","r");g=fopen("pscpld.out","w");
	sir[0]='#';
	s=&sir[1];fscanf(f,"%s",s);
	L=strlen(s);
	for(i=L-1;i>=0;i--){ s[2*i+2]=' ';s[2*i+1]=s[i];}
	s[0]=' ';
	na=2;
	L=2*L;s[L+1]='*';
	for(i=1;i<L;i++)
	{
	  while(s[i+lung[i]+1]==s[i-lung[i]-1])lung[i]++;
	  if(na<i+lung[i])
	  { for(dr=na;dr<=i+lung[i];dr++)
	    { st=2*i-dr;
	      if(st-lung[st]>=i-lung[i])lung[dr]=lung[st];
	      else
	      lung[dr]=i+lung[i]-dr;
	    }
	    na=i+lung[i]+1;
	}
	  sol=sol+(lung[i]+i%2)/2;
	}
	fprintf(g,"%ld\n",sol);
	return 0;
}