Pagini recente » Cod sursa (job #2191543) | Cod sursa (job #2828645) | Cod sursa (job #455863) | Cod sursa (job #2420909) | Cod sursa (job #209998)
Cod sursa(job #209998)
#include<fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int urm[1000],t[1000],p[1000],n,m,lg;
void citire()
{in>>n>>m;
for(int i=0;i<n;i++)
in>>t[i];
for(int i=0;i<m;i++)
in>>p[i];}
void prefix()
{int k=-1,x;
for(x=1;x<m;x++)
{while(k>0 && p[k+1]!=p[x]) k=urm[k];
if(p[k+1]==p[x]) k++;
urm[x]=k;} }
int main()
{citire();
int i,q=-1;
prefix();
lg=0;int lung[1000];
for(i=0;i<n;i++)
{while(q>-1 && p[q+1]!=t[i]) q=urm[q];
if(p[q+1]==t[i]) q++;
if(q==m-1) {lg++;lung[lg]=i-m+1;}
}
out<<lg<<'\n';
for(int j=1;j<=lg;j++)
out<<lung[j]<<" ";
return 0;}