Cod sursa(job #695273)

Utilizator Marius96Marius Gavrilescu Marius96 Data 28 februarie 2012 11:35:40
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<cstdio>
#include<cstring>
char a[2000005],b[2000005];
int r[1005],nr;
int lg=0;
struct hash
{
	int v;
	int bston;
	static const int bs=43;//maximum possible digit is 'Z'-'0' == 42
	static const int md=11027;//random prime
	hash (char * s){
		v=0;
		bston=1;
		if(!lg)
			lg=strlen (s);
		for(int i=0;i<lg;i++)
			(*this)+=s[i];
	}
	bool operator==(hash h)
	{
		return v==h.v;
	}
	void operator-=(int x)
	{
		x-='0';

		while(bston%bs)
			bston+=md;
		bston/=bs;

		v-=x*bston;
		while(v<0)
			v+=md;
		v%=md;
	}
	void operator+=(int x)
	{
		x-='0';
		bston=(bston*bs)%md;
		v=(v*bs+x)%md;
	}
};

void rabinkarp()
{
	hash ha (a),hb (b);
	for(int i=0;i<strlen (b)-strlen (a)+1;i++){
		if(ha==hb)
			if((strncmp (a,b+i,strlen (a))==0)){
			if(nr<1000)
				r[nr]=i;
			nr++;
		}
		hb-=b[i];
		hb+=b[i+strlen (a)];
	}
}
int main()
{
	freopen ("strmatch.in","r",stdin);
	freopen ("strmatch.out","w",stdout);
	gets (a);
	gets (b);
	rabinkarp();
	printf ("%d\n",nr);
	for(int i=0;i<nr&&i<1000;i++)
		printf ("%d ",r[i]);
	return 0;
}