Cod sursa(job #369725)

Utilizator titusuTitus C titusu Data 29 noiembrie 2009 13:15:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
using namespace std;
#include <fstream>
#include <iostream>
#define MAX 2000010
#define nrLitere (26+26+10)
#define nrPrim 100021
char s[MAX], p[MAX];
int ns,np;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

void read();
void solve();
void write();
int ord(char c);
int main(){
		read();
		/*
		for(int i=1;i<=np;i++)
			cout<<p[i];
		cout<<endl;
		for(int i =1;i<=ns;i++)
			cout<<s[i];
		cout<<endl;
		*/
		solve();
		write();
		return 0;
	}

int isOk(char c){
	if(c>='A' && c<='Z')
		return 1;
	if(c>='a' && c<='z')
		return 1;
	if(c>='0' && c<='9')
		return 1;
	return 0;
}

void read(){
	np=0;
	char x;
	x=fin.get();
	while(isOk(x)){
		p[++np]=x;
		x=fin.get();
	}
	while(!isOk(x))
		x = fin.get();
	ns=0;
	while(isOk(x)){
		s[++ns] = x;
		x=fin.get();
	}
}

int nrpoz, nrpp, poz[1010];

void solve(){
	int dlam_1=1; //(d=nrLitere)^(np-1)
	for(int i=1;i<np;++i)
		dlam_1 =(dlam_1 *nrLitere) % nrPrim;
	int hp=0 ; //hasul lui p
	for(int i=1;i<=np;i++)
		hp = (hp * nrLitere + ord(p[i])) % 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 * nrLitere + ord(s[i])) % nrPrim;
	for(int i=1;i<=ns-np+1;++i){
		//cout<<i<<" "<<s[i]<<" "<<hs<<endl;
		//verific protrivirea
		if(hp ==hs && s[i+np-1]==p[np]){
			nrpoz++;
			if(nrpoz<=1000)
				poz[++nrpp]=i-1;
		}
		hs = (hs + nrLitere*nrPrim-(ord(s[i])*dlam_1)%nrPrim)%nrPrim;
		hs = (hs*nrLitere+ord(s[i+np])) % nrPrim;
	}
}

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

int ord(char c){
	if(c<='9')
		return c-'0';
	if(c<='Z')
		return 10+c-'A';
	return 10+26+c-'a';
}