Cod sursa(job #1301621)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 26 decembrie 2014 11:17:54
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#include <string>

const long long mod1=3037000493, mod2=3037000453, base=75;

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

	std::string p,t; //pattern and text
	fin>>p>>t;

	if(p.size()>t.size()) fout<<"0\n\n";
	else{
		long long hp1=0,hp2=0;
		long long ht1=0,ht2=0;

		long long mostsig1=1,mostsig2=1;
		for(unsigned i=1;i<p.size();++i){
			mostsig1=mostsig1*base%mod1;
			mostsig2=mostsig2*base%mod2;
		}

		for(unsigned i=0;i<p.size();++i){
			hp1 = (hp1*base + p[i])	% mod1;
			hp2 = (hp2*base + p[i])	% mod2;

			ht1 = (ht1*base + t[i])	% mod1;
			ht2 = (ht2*base + t[i])	% mod2;
		}

		unsigned nr=0;
		unsigned out[1000];


		if(hp1==ht1&&hp2==ht2){
			out[nr++]=0;
		}

		for(unsigned i=p.size();i<t.size();++i){
			ht1=( ( ht1 - mostsig1*t[i-p.size()] )*base + t[i] )%mod1;
			ht2=( ( ht2 - mostsig2*t[i-p.size()] )*base + t[i] )%mod2;

			if(hp1==ht1&&hp2==ht2){
				if(nr<1000) out[nr]=i-p.size()+1;
				++nr;
			}
		}

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