Cod sursa(job #157668)

Utilizator razvi9Jurca Razvan razvi9 Data 13 martie 2008 10:39:26
Problema Prefix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include<cstdio>
#include<cstring>
using namespace std;
const int size=50;
int pi[size];
char a[size];
int n,i,k,t,lg;

bool isperiodic()
{
	if(pi[i]==-1) return 0;
	if((i+1)%(i-pi[i])==0) return 1;
	return 0;
}

inline void solve()
{
	gets(a);
	n=strlen(a);
	k=-1;
	pi[0]=-1;
	for(i=1;i<n;++i){
		while(k>=0 && a[k+1]!=a[i])
			k=pi[k];
		if(a[k+1]==a[i]) ++k;
		pi[i]=k;}
	lg=0;
	for(i=n-1;i>0;--i)
		if(isperiodic()) {lg=i+1;break;}
	printf("%d\n",lg);
}

int main()
{
	freopen("prefix.in","r",stdin);
	freopen("prefix.out","w",stdout);
	scanf("%d ",&t);
	for(;t;--t)
		solve();
	fclose(stdout);
	return 0;
}