Cod sursa(job #635825)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 19 noiembrie 2011 15:02:59
Problema PalM Scor 20
Compilator cpp Status done
Runda .com 2011 Marime 1.3 kb
#include <cstdio>
#include <cstring>
#define nmax 510

char s[nmax];
int n, a[nmax], right[nmax], len[nmax], sol;

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

int main()
{
	freopen("palm.in","r",stdin);
	freopen("palm.out","w",stdout);
	int i, st, dr, x;
	fgets(s, nmax, stdin);
	n=strlen(s);
	for (i=n; i>0; i--) s[i]=s[i-1];
	a[1]=1;
	for (i=2; i<=n; i++)
		if (s[i]>=s[i-1]) a[i]=a[i-1]+1; else
			a[i]=1;
	right[n]=1;
	for (i=n-1; i>0; i--)
		if (s[i]>=s[i+1]) right[i]=right[i+1]+1; else
			right[i]=1;
	st=dr=0;
	for (i=1; i<=n; i++)
	{
		if (dr>i)
			len[i]=min(len[st+dr-i], dr-i+1);
		if (i+len[i]-1>=dr)
		{
			dr=i+len[i]-1;
			st=i-len[i]+1;
			while (s[st-1]==s[dr+1] && dr<n && st>1)
			{
				st--;
				dr++;
				len[i]++;
			}
		}
	}
	for (i=1; i<=n; i++)
	{
		x=min(a[i], right[i]);
		x=min(x, len[i]);
		if (2*x-1>sol) sol=2*x-1;
	}
	st=dr=0;
	for (i=1; i<=n; i++) len[i]=0;
	for (i=1; i<n; i++)
	{
		if (dr>i)
			len[i]=min(len[st+dr-i-1], dr-i);
		if (i+len[i]>=dr)
		{
			dr=i+len[i];
			st=i-len[i]+1;
			while (s[st-1]==s[dr+1] && dr<n && st>1)
			{
				st--;
				dr++;
				len[i]++;
			}
		}
	}
	for (i=1; i<n; i++)
	{
		x=min(a[i], right[i+1]);
		x=min(x, len[i]);
		if (2*x>sol) sol=2*x;
	}
	printf("%d\n",sol);
}