Cod sursa(job #715067)

Utilizator GrimpowRadu Andrei Grimpow Data 16 martie 2012 16:29:35
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<cstdio>
#include<cstring>
char b[1000001],a[2000001];
int n,i,lg=1,poz=1,s[2000001];
long long nr;
int m(int a,int b)
{
	if(a<b) return a;
	return b;
}
int main()
{
	freopen("pscpld.in","r",stdin);
	freopen("pscpld.out","w",stdout);
	gets(b);
	s[0]=1;
	n=strlen(b);
	for(i=0;i<n;i++){
		a[2*i+1]=b[i];
		a[2*i]=' ';}
	n=2*n-1;
	s[1]=1;
	nr=1;
	for(i=2;i<=n;i++){
		s[i]=1;
		if(poz+lg-1>i)
			s[i]=m(poz+lg-i,s[2*poz-i]);
		while(i-s[i]>0 && a[i-s[i]]==a[i+s[i]]) s[i]++;
		if(i%2)
			nr+=(s[i]+1)/2;
		else
			nr+=s[i]/2;
		if(s[i]+i>poz+lg) poz=i,lg=s[i];}
	printf("%lld\n",nr);
	fclose(stdout);
	return 0;
}