Cod sursa(job #209998)

Utilizator Bogdan_CCebere Bogdan Bogdan_C Data 25 septembrie 2008 22:27:34
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.6 kb
#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;}