Cod sursa(job #123270)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 15 ianuarie 2008 11:23:05
Problema PScPld Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include<stdio.h>
#include<string.h>
char *s,sir[2000005];
long int i,j,e[2000005],viz[2000005],ll,pc,ec,sc,ps,ss,pd,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++)
	 if(!viz[pc])
	  { ec=0;
	    while(pc+ec+1<=ll&&pc-ec-1>=0&&s[pc+ec+1]==s[pc-ec-1])ec++;
	    sc=pc-ec;e[pc]=ec;
	    for(i=1;i<=ec;i++)
	    { ps=pc-i;ss=ps-e[ps];
	      if(ss>=sc)
	      { pd=pc+i;e[pd]=e[ps];viz[ps]=1;}
	    }
	    viz[pc]=1;
	  }
	for(pc=1;pc<ll;pc=pc+2) e[pc]++;
        for(pc=1;pc<ll;pc++)sol+=e[pc];
        sol/=2;
	fprintf(g,"%ld\n",sol);
	return 0;
}