Cod sursa(job #114291)

Utilizator VmanDuta Vlad Vman Data 13 decembrie 2007 18:24:27
Problema Prefix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <stdio.h>
#include <string.h>

#define Lmax 1000005

int T,N;
char S[Lmax];
int P[Lmax];

void pattern()
{
 int i,k;
 memset(P,0,sizeof(P));
 P[0]=-1;
 k=-1;
 for (i=1;i<N;++i)
	{
	 while ((k>-1)&&(S[k+1]!=S[i]))
		k=P[k];
	 if (S[k+1]==S[i]) ++k;
	 P[i]=k;
	}
}

void doit()
{
 int i,delta,max=0;
 pattern();
 for (i=0;i<N;++i)
	{
	 if (P[i]+1<(i+1)/2) continue;
	 delta=i-P[i];
	 if ((i+1)%delta==0) max=i+1;
	}
 if (max!=1) printf("%d\n",max);
    else printf("%d\n",0);
}

int main()
{
 freopen("d:/programe/bc/bin/prefix.in","r",stdin);
 freopen("prefix.out","w",stdout);
 scanf("%d",&T);
			   while (T>0)
	{
	 scanf("%s\n",&S);
	 N=strlen(S);
	 doit();
         --T;
	}
 fclose(stdin);
 fclose(stdout);
 return 0;
}