Cod sursa(job #2288282)

Utilizator Andrei_RAndrei Roceanu Andrei_R Data 23 noiembrie 2018 00:06:43
Problema Prefix Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("prefix.in");
ofstream out("prefix.out");
char a[2000100],x;
int i,n,m,k,j,nr,q,t,Max;
int p[2000100];
int main()
{
    in>>t;
    for(q=1;q<=t;q++)
    {
    Max=0;
    in>>a;
    n=strlen(a);
    for(i=n;i>0;i--)
        a[i]=a[i-1];
    j=0;
    i=2;
    p[1]=0;
    while(i<=n)
    {
       while(a[i]!=a[j+1]&&j>0) j=p[j];
       if(a[i]==a[j+1])
           j++;
       p[i]=j;
       i++;
    }
     for(i=1;i<=n;i++)
     {
         if(i%(i-p[i])==0&&p[i]>0)
            if(i>Max) Max=i;
     }
     out<<Max<<'\n';
 
    }
    return 0;
}