Cod sursa(job #369707)

Utilizator titusuTitus C titusu Data 29 noiembrie 2009 12:27:25
Problema Potrivirea sirurilor Scor 2
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
using namespace std;
#include <fstream>
#include <iostream>
#define MAX 2000010
#define nrPrim 666666667
char s[MAX], p[MAX];
int ns,np;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

void read();
void solve();
void write();
int main(){
		read();
		solve();
		write();
		return 0;
	}

void read(){
	np=0;
	char x;
	x=fin.get();
	while(x>='A' && x<='Z'){
		p[++np]=x;
		x=fin.get();
	}
	while(x<'A' || x>'Z')
		x = fin.get();
	ns=0;
	while(x>='A' && x<='Z'){
		s[++ns] = x;
		x=fin.get();
	}
}

int nrpoz, nrpp, poz[1010];

void solve(){
	int dlam_1=1; //(d=26)^(m-1)
	for(int i=1;i<np;++i)
		dlam_1 =(dlam_1 *26) % nrPrim;
	int hp=0 ; //hasul lui p
	for(int i=1;i<=np;i++)
		hp = (hp * 26 + p[i]-'A'+1) % nrPrim;
	cout<<"hp = "<<hp<<endl;
	int hs = 0; // hasul lui s1s2...snp, se modifica mai tarziu
	for(int i=1;i<=np;i++)
		hs = (hs * 26 + s[i]-'A'+1) % nrPrim;
	for(int i=1;i<=ns-np+1;++i){
		//cout<<i<<" "<<s[i]<<" "<<hs<<endl;
		//verific protrivirea
		if(hp ==hs){
			nrpoz++;
			if(nrpoz<=1000)
				poz[++nrpp]=i-1;
		}
		hs = (hs-(s[i]-'A'+1)*dlam_1)%nrPrim;
		hs = (hs*26+s[i+np]-'A'+1) % nrPrim;
	}
}

void write(){
	fout<<nrpoz<<endl;
	for(int i=1;i<=nrpp;++i)
		fout<<poz[i]<<" ";
}