Cod sursa(job #590802)
Utilizator | Enal Gemaledin Blaugranas | Data | 20 mai 2011 09:58:43 |
---|---|---|---|
Problema | Prefix | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.54 kb |
#include<fstream.h>
#define N 10000000
char s[N],w[N];
long n,k,p[N],i,j,q,r[N],max,l,d,v[N],u,t;
int main()
{ifstream f("prefix.in");
ofstream g("prefix.out");
f>>t;
for(;!f.eof();f.get())
{f>>s;
n=strlen(s);
if(f.good())
{k=q=l=p[1]=r[1]=u=max=0;
for(i=2;i<n;i++)
{while(k>0&&s[k+1]!=s[i])
k=p[k];
if(s[k+1]==s[i])
k++;
p[i]=k;
if(p[i]>max)
{max=p[i];
j=i-max;}}
for(i=0;i<j;i++)
w[i]=s[i];
for(i=2;i<j;i++)
{while(q>0&&w[q+1]!=w[i])
q=r[q];
if(w[q+1]==w[i])
q++;
r[i]=q;}
for(i=1;i<n;i++)
{while(l>0&&w[l+1]!=s[i])
l=r[l];
if(w[l+1]==s[i])
l++;
if(l==j-1&&w[0]==s[i-l])
v[++u]=i-j+1;}
d=v[1]+j;
for(i=2;i<=u;i++)
if(v[i]-v[i-1]==j)
d=v[i]+j;
else
break;
g<<d<<'\n';}}
f.close();
g.close();
return 0;}