Cod sursa(job #1312054)
Utilizator | Duiu Octavian Octa | Data | 8 ianuarie 2015 20:48:19 |
---|---|---|---|
Problema | Prefix | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.73 kb |
#include<cstdio>
#include<algorithm>
#include<cstring>
int t,n,i,j,v[1000003];
char S[1000003];
void prefix()
{
j=0;
v[1]=0;
for (i=2;i<=n;i++)
{
while(j && S[i]!=S[j+1]) j=v[j];
if(S[i]==S[j+1]) j++;
v[i]=j;
}
}
int main()
{
freopen("prefix.in","r",stdin);freopen("prefix.out","w",stdout);
scanf("%d\n",&t);
while(--t)
{
bool ok=false;
gets(S+1);
n=strlen(S+1);
prefix();
for(i=n;i>0;i--)
if( v[i]&& !(i%(i-v[i])))
{
printf("%d\n",i);
ok=true;
break;
}
if(!ok) printf("%d\n",0);
}
return 0;
}