Cod sursa(job #990270)

Utilizator horatiu11Ilie Ovidiu Horatiu horatiu11 Data 27 august 2013 20:28:24
Problema Prefix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
# include <iostream>
# include <cstdio>
# include <cstring>
using namespace std;
int t,i,pi[1000001],j,n,k,sol;
char x[1000001];
void constr_pi()
{
    pi[1]=0;
    for(i=2;i<=n;++i)
    {
        while(k>0 && x[i]!=x[k+1])
            k=pi[k];
        if(x[k+1]==x[i])++k;
        pi[i]=k;
    }
    sol=0;
    for(i=n;i>1;--i)
        if( (pi[i]) && (i%(i-pi[i])==0) ){sol=i;break;}
}
int main()
{
    freopen("prefix.in","r",stdin);
    freopen("prefix.out","w",stdout);
    scanf("%d",&t);
    cin.get();
    for(j=1;j<=t;++j)
    {
        gets(x+1);n=strlen(x+1);
        k=0;
        constr_pi();
        printf("%d\n",sol);
    }
    return 0;
}