Cod sursa(job #928800)

Utilizator dariusdariusMarian Darius dariusdarius 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;
}