Cod sursa(job #2048510)
Utilizator | Data | 26 octombrie 2017 09:49:21 | |
---|---|---|---|
Problema | Prefix | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.48 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream f("prefix.in"); ofstream g("prefix.out");
int nrt,phi[1000010];
char P[1000010];
int main()
{ f>>nrt;
while(nrt--)
{ f>>(P+1);
phi[1]=0;
int m=strlen(P+1),ma=0,k=0;
for(int i=2; i<=m; ++i)
{ while(k && P[k+1]!=P[i]) k=phi[k];
if(P[i]==P[k+1]) k++;
phi[i]=k;
if(k && i%(i-k)==0) ma=i;
}
g<<ma<<'\n';
}
return 0;
}