Cod sursa(job #114324)

Utilizator tm_raduToma Radu tm_radu Data 13 decembrie 2007 19:50:43
Problema PScPld Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <stdio.h>

int n, i, j, k;
int l[2000001];
char c;
int s[1000001];
int sol;
inline int Min(int i, int j) { return i < j ? i : j; }

int main()
{
	freopen("pscpld.in", "r", stdin);
	freopen("pscpld.out", "w", stdout);
	c = '#';
	n = 0;
	scanf("%c", &c);
	while ( c != '\n' )
	{
		n++, s[n] = (int)(c-'a'+1);
		c = '#';
		scanf("%c", &c);
	}
	for ( i = 1; i <= 2*n; i++ )
		if ( i % 2 == 1 )
		{
			j = l[i];
			k = (i+1)/2;
			while ( k-j >= 1 && k+j <= n && s[k-j] == s[k+j] )
				j++;
			l[i] = j;
			for ( j = 1; j < 2*l[i]-1; j++ )
				if ( (i+j)%2 == 1 ) l[i+j] = Min(l[i-j], l[i]-j/2);
				else                l[i+j] = Min(l[i-j], l[i]-(j+1)/2);
		}
		else
		{
			j = l[i];
			k = i/2;
			while ( k-j >= 1 && k+j+1 <= n && s[k-j] == s[k+j+1] ) j++;
			l[i] = j;
			for ( j = 1; j < 2*l[i]; j++ )
				if ( (i+j) % 2 == 1 ) l[i+j] = Min(l[i-j], l[i]-j/2);
				else                  l[i+j] = Min(l[i-j], l[i]-j/2);
		}
	for ( i = 1; i <= 2*n; i+=2 )
		if ( sol < 2*l[i]-1 ) sol = 2*l[i]-1;
	for ( i = 2; i <= 2*n; i+= 2 )
		if ( sol < 2*l[i] ) sol = 2*l[i];
    printf("%d\n", sol);
    
    return 0;
}