Cod sursa(job #733328)
Utilizator | FMI-Alex Dobrin Barracuda | Data | 11 aprilie 2012 20:47:33 |
---|---|---|---|
Problema | Prefix | Scor | 90 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.54 kb |
#include<fstream>
#include<cstring>
#define dim 1000004
using namespace std;
ifstream f("prefix.in");
ofstream g("prefix.out");
char s[dim];
int p[dim],k,i,t,n;
void prefix(){
p[1]=0;
k=0;
int i;
int maxu=0;
for(i=2;s[i]!=0;i++){
while( k>0 && s[k+1]!=s[i] )
k=p[k];
if(s[k+1]==s[i])
k++;
if(k>0 && i%(i-k)==0)
maxu=i;
p[i]=k;
}
g<<maxu<<"\n";
}
int main () {
f>>t;
f.get();
for( ; t ; t-- ) {
f>>(s+1);
prefix();
}
return 0;
}