Cod sursa(job #144776)

Utilizator ProtomanAndrei Purice Protoman Data 27 februarie 2008 22:39:09
Problema Prefix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <stdio.h>
#include <string.h>
#define mx 1000010
long i,t,rz;
long pi[mx],pik[mx],v[mx];
char s[mx+4];

void vf(int i)
{
	if (pi[i]<<1==i)
	{
		v[i]=1;
		pik[i]=pi[i];
	}
	else if (v[i-pik[pi[i]]]==1)
	{
		v[i]=1;
		pik[i]=pik[pi[i]];
	}
	if (v[i]==1)
		rz=i;
}

void prefix()
{
	long i,n,p;
	n=strlen(s+1)-1;
	p=0;
	rz=0;
	for (i=2; i<=n; i++)
	{
		while (p>0 && s[i]!=s[p+1])
			p=pi[p];
		if (s[i]==s[p+1])
			p++;
		pi[i]=p;
		if (pi[i]>0)
			vf(i);
	}
	for (i=1; i<=n; i++)
	{
		v[i]=0;
		pik[i]=0;
		pi[i]=0;
	}
}

int main()
{
	freopen("prefix.in","r",stdin);
	freopen("prefix.out","w",stdout);
	scanf("%ld\n",&t);
	for (i=0; i<t; i++)
	{
		fgets(s+1,mx,stdin);
		prefix();
		printf("%ld\n",rz);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}