Cod sursa(job #84768)

Utilizator DITzoneCAdrian Diaconu DITzoneC Data 16 septembrie 2007 22:32:42
Problema PScPld Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <stdio.h>
#include <string.h>

#define nmax 2111000
#define FOR(i,s,d) for(i=(s);i<(d);++i)

char s[nmax];
int n,poz,l,last,start,L[nmax];
long long sol;

inline int min(int a,int b) {return a<b?a:b;}

int main()
{
	int i;
	freopen("pscpld.in","r",stdin);
	freopen("pscpld.out","w",stdout);
	scanf("%s",s);
	n=strlen(s);
	for(i=n;i>=0;--i)
		s[2*i+1]=s[i],s[2*i]='#';
	n=2*n+1;

	poz=0, last=0, L[0]=0;
	FOR(i,1,n)
	{
		if(last>=i)
			L[i]=min(L[poz+poz-i],last-i);
		else
			L[i]=0;
		for(;i+L[i]+1<n&&i-L[i]-1>=0&&s[i-L[i]-1]==s[i+L[i]+1];L[i]++);			
		if(i+L[i]>last)
			last=i+L[i],poz=i;
		sol+=(s[i]=='#'?(L[i]+1)/2:L[i]/2+1);
	}	
	printf("%lld\n",sol);
	return 0;
}