Cod sursa(job #841104)
Utilizator | Alex Cociorva Al3ks1002 | Data | 23 decembrie 2012 19:39:40 |
---|---|---|---|
Problema | Prefix | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.6 kb |
#include<cstdio>
#include<cstring>
using namespace std;
const int smax = 1000005;
int t,n,pi[smax];
char S[smax];
int prefix()
{
int q=0,i;
pi[1]=0;
for(i=2;i<=n;i++)
{
while(q>0 && S[q+1]!=S[i]) q=pi[q];
if(S[q+1]==S[i]) q++;
pi[i]=q;
}
for(;i;i--)
if(pi[i] && !(i%(i-pi[i]))) break;
return i;
}
int main()
{
freopen("prefix.in","r",stdin);
freopen("prefix.out","w",stdout);
scanf("%d\n",&t);
for(;t;t--)
{
gets(S+1);
n=strlen(S+1);
printf("%d\n",prefix());
}
return 0;
}