Cod sursa(job #1301646)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 26 decembrie 2014 11:40:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>

const unsigned MAXN=2000001;
//const int mod1=3037000493, mod2=3037000453, base=75;
const int mod1=46337, mod2=46327, base=75;

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

	char p[MAXN],t[MAXN]; //pattern and text
	fin.get(p,MAXN); fin.get();
	fin.get(t,MAXN);

	unsigned ps=0,ts=0;
	while(p[ps]) p[ps++]-='0';
	while(t[ts]) t[ts++]-='0';

	if(ps>ts) fout<<"0\n\n";
	else{
		int hp1=0,hp2=0;
		int ht1=0,ht2=0;

		int mostsig1=1,mostsig2=1;
		for(unsigned i=1;i<ps;++i){
			mostsig1=mostsig1*base%mod1;
			mostsig2=mostsig2*base%mod2;
		}

		for(unsigned i=0;i<ps;++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=ps;i<ts;++i){
			ht1=(((ht1 - mostsig1*t[i-ps])%mod1+mod1 )*base + t[i] )%mod1;
			ht2=(((ht2 - mostsig2*t[i-ps])%mod2+mod2 )*base + t[i] )%mod2;

			if(hp1==ht1&&hp2==ht2){
				if(nr<1000) out[nr]=i-ps+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';
	}
}