Cod sursa(job #927404)
Utilizator | Stepan Patrik Patrik | Data | 25 martie 2013 19:42:50 |
---|---|---|---|
Problema | Prefix | Scor | 90 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.79 kb |
#include<cstdio>
#include<fstream>
using namespace std;
#define MAX 1000005
int T , pi[MAX] , q , maxx;
char s[MAX];
int main()
{
ifstream f("prefix.in");
ofstream g("prefix.out");
f>>T;
for(int i = 1 ; i <= T ; ++i )
{
f>>(s+1);
pi[0] = pi[1] = maxx = 0;
q = 0;
for(int i = 2 ; s[i] ; ++i )
{
while(s[i]!=s[q+1] && q)
q = pi[q];
if(s[i] == s[q+1])
q++;
pi[i] = q;
if(pi[i] && pi[i]%(i-pi[i])==0)
maxx = i;
}
g<<maxx<<"\n";
}
f.close();
g.close();
return 0;
}