Cod sursa(job #476561)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 11 august 2010 15:50:12
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>
#include <cstring>
#define nmax 1000010

char s[nmax];
int v[2*nmax], n, t;

int min(int a, int b)
{
	if (a>b) a=b;
	return a;
}

int max(int a, int b)
{
	if (a<b) a=b;
	return a;
}

int main()
{
	freopen("pscpld.in","r",stdin);
	freopen("pscpld.out","w",stdout);
	scanf("%s",s);
	n=strlen(s);
	int i, k, j, c, x;
	for (i=n; i>0; i--) s[i]=s[i-1];
	for (i=1; i<=n; i++)
	{
		k=v[2*i-1];
		for (j=k+1; j<=n-i+1 && j<=i; j++)
		{
			if (s[i+j-1]!=s[i-j+1]) break;
			k=j;
		}
		v[2*i-1]=k;
		for (j=1; j<k; j++)
		{
			x=i+j-1;
			c=min(v[2*(i-j)],j);
			c=min(c,k-j);
			v[2*x]=max(v[2*x],c);
			
			c=min(v[2*(i-j)-1], j+1);
			c=min(c,k-j);
			v[2*x+1]=max(v[2*x+1],c);
		}
			
		k=v[2*i];
		for (j=k+1; j<=n-i && j<=i; j++)
		{
			if (s[i+j]!=s[i-j+1]) break;
			k=j;
		}
		v[2*i]=k;
		if (k)
		{
			c=min(v[2*i-1],1);
			v[2*i+1]=max(v[2*i+1],c);
		}
		for (j=1; j<k; j++)
		{
			x=i+j;
			c=min(v[2*(i-j)],j);
			c=min(c,k-j);
			v[2*x]=max(v[2*x], c);
			
			c=min(v[2*(i-1)-1], j+1);
			c=min(c, k-j);
			v[2*x+1]=max(v[2*x+1], c);
		}
	}
	for (i=1; i<=2*n; i++) t+=v[i];
	printf("%d\n",t);
}