Cod sursa(job #190554)
Utilizator | Data | 23 mai 2008 09:06:16 | |
---|---|---|---|
Problema | Prefix | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.5 kb |
#include<stdio.h>
#define Nmax 1000010
#define IN "prefix.in"
#define OUT "prefix.out"
int maxp,t;
char c[Nmax];
int pi[Nmax];
void prefix()
{
int k=0;
for(int i=2;c[i]!='\0';++i)
{
while(k>0 && c[k+1]!=c[i])
k=pi[k];
if(c[i]==c[k+1])
++k;
pi[i]=k;
if(pi[i]!=0 && !(pi[i]%(i-pi[i])) )
maxp=i;
}
}
int main()
{
freopen(IN,"r",stdin);
freopen(OUT,"w",stdout);
scanf("%d\n",&t);
for(int ti=1;ti<=t;++ti)
{
gets(c+1);
prefix();
printf("%d\n",maxp);
}
return 0;
}