Cod sursa(job #123481)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 16 ianuarie 2008 09:42:29
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 i,j,lung[2000005],ll,pc,st,dr,sol;
int main()
{
	FILE *f,*g;f=fopen("pscpld.in","r");g=fopen("pscpld.out","w");
	s=&sir[0];fscanf(f,"%s",s);
	ll=strlen(s);
	for(i=ll-1;i>=0;i--){s[2*i+1]=s[i];s[2*i+2]=' ';}s[0]=' ';ll=ll*2;
	for(pc=1;pc<ll;pc++)
	 { st=pc-lung[pc]-1;dr=pc+lung[pc]+1;
	   while(st>=0&&dr<=ll&&s[st]==s[dr]){lung[pc]++;st--;dr++;}
	   for(i=1;i<=lung[pc];i++)
	    if(pc-i-lung[pc-i]>=pc-lung[pc])
	     if(lung[pc+i]<lung[pc-i])
	      lung[pc+i]=lung[pc-i];
	   if(pc%2)sol=sol+(lung[pc]+1)/2;
           else sol=sol+lung[pc]/2;
	 }
	fprintf(g,"%ld\n",sol);
	return 0;
}