Cod sursa(job #1305979)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 30 decembrie 2014 13:42:45
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
//KMP
#include <fstream>
#include <string>
#include <vector>

int main(){
	std::ifstream fin("strmatch.in");
	std::ofstream fout("strmatch.out");

	std::string P,T; fin>>P>>T;

	unsigned m=P.size();
	unsigned n=T.size();

	//compute the table
	std::vector<unsigned> prefix(m);
	prefix[0]=0;
	unsigned k=0;
	for(unsigned i=1;i<m;++i){
		while(k>0&&P[i]!=P[k]) k=prefix[k-1];
		if(P[i]==P[k]) ++k;
		prefix[i]=k;
	}

	unsigned nr=0;
	unsigned matches[1000];

	//check the string
	unsigned q=0; //number of characters matched
	for(unsigned i=0;i<n;++i){
		while(q>0&&P[q]!=T[i]) q=prefix[q];
		if(P[q]==T[i]) ++q;
		if(q==m){
			if(nr<1000){ matches[nr]=i+1-m; }
			++nr;

			q=prefix[q-1];
		}
	}

	fout<<nr<<'\n';
	unsigned nrm=1000;
	if(nr<1000) nrm=nr;
	for(unsigned i=0;i<nrm;++i) fout<<matches[i]<<' ';
	fout<<'\n';
}