Cod sursa(job #887650)

Utilizator Marius96Marius Gavrilescu Marius96 Data 23 februarie 2013 23:03:09
Problema PScPld Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include<cstdio>
#include<cstring>

#define min(a,b) ((a)<(b)?(a):(b))

char s[2000005];
int  d[2000005];

int main (void)
{
	freopen ("pscpld.in","r",stdin);
#ifdef INFOARENA
	freopen ("pscpld.out","w",stdout);
#endif

	gets (s);
	int n=strlen (s);
	for(int i=2*n;i>=0;i--)
		s[i]=i%2?s[i/2]:'!';
	n=n*2+1;

	int mx=0;
	for(int i=0;i<n;i++){
		if(mx+d[mx]>=i)
			d[i]=min (mx+d[mx]-i, d[2*mx-i]);
		while(i-d[i]>=0&&i+d[i]<n&&s[i-d[i]]==s[i+d[i]])
			d[i]++;
		if(i+d[i]>=mx+d[mx])
			mx=i;
	}

	int ret=0;
	for(int i=0;i<n;i++)
		if(i%2)
			ret+=(d[i]+1)/2;
		else
			ret+=d[i]/2;

	printf ("%d",ret);
	return 0;
}