Cod sursa(job #290201)

Utilizator tibiletsKoos Tiberiu Iosif tibilets Data 27 martie 2009 16:52:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<fstream.h>
#include<string.h>
char A[2000002],B[2000002];
int pi[2000002],p[1001],m,n,q,i,nr;
void cpi()
{int k=0;
 for(q=2;q<=m;++q)
 {while(k>0&&A[k+1]!=A[q])
   k=pi[k];
  if(A[k+1]==A[q])
   ++k;
  pi[q]=k;
 }
}
int main()
{ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.get(A,2000002);f.get();
f.get(B,2000002);
m=strlen(A);
n=strlen(B);
for(i=m;i;--i)A[i]=A[i-1];
for(i=n;i;--i)B[i]=B[i-1];
cpi();
q=0;
for(i=1;i<=n;++i)
{while(q>0&&A[q+1]!=B[i])
  q=pi[q];
 if(A[q+1]==B[i])
  ++q;
 if(q==m)
 {q=pi[q];
  ++nr;
  if(nr<1001)
   p[nr]=i-m;
 }
}
g<<nr<<"\n";
if(nr>1000)nr=1000;
for(i=1;i<=nr;++i)
 g<<p[i]<<' ';
return 0;
}