Cod sursa(job #2106258)
Utilizator | andrei contor andreicontor | Data | 15 ianuarie 2018 15:45:18 |
---|---|---|---|
Problema | Prefix | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.69 kb |
#include<cstdio>
#include<cstring>
#include<fstream>
using namespace std;
ifstream f("prefix.in");
ofstream g("prefix.out");
int t,l,q,i,n,j,poz,k,urmator[1000001];
char s[1000001];
void prefix()
{
k=0;
urmator[1]=0;
t=strlen(s);
for(q=2;q<=t;q++)
{
while(k>0&&s[q]!=s[k+1])
k=urmator[k];
if(s[q]==s[k+1])
k++;
urmator[q]=k;
}
}
int main()
{
f>>n;
for(i=1;i<=n;i++)
{
f>>s+1;
s[0]='*';
prefix();
l=strlen(s);
for(j=1;j<=l;j++)
if(j%(j-urmator[j])==0&&urmator[j]!=0)
poz=j;
g<<poz<<'\n';
}
return 0;
}