Cod sursa(job #695540)

Utilizator Marius96Marius Gavrilescu Marius96 Data 28 februarie 2012 12:52:25
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include<cstdio>
#include<cstring>
char a[2000005],b[2000005];
int r[1005],nr;
int lg=0;
int bston[2000005];
const long long bs=75;//maximum possible digit is 'z'-'0' == 74
const long long md=666013;//Infoarena-approved Big Prime
struct hash
{
	long long v;
	int bstoni;
	hash (char * s){
		v=0;
		bstoni=0;
		if(!lg)
			lg=strlen (s);
		for(int i=0;i<lg;i++)
			(*this)+=s[i];
	}
	bool operator==(hash h)
	{
		return v==h.v;
	}
	inline void operator-=(int x)
	{
		v=(v+md-((x-'0')*bston[--bstoni])%md)%md;
	}
	inline void operator+=(int x)
	{
		x-='0';
		bstoni++;
		v=(v*bs+x)%md;
	}
};
int nr1,nr2;
int n,m;
void rabinkarp()
{
	hash ha (a),hb (b);

	for(int i=0;i<m-n+1;i++){
		if(ha==hb){
//			nr1++;
			if((strncmp (a,b+i,n)==0)){
//				nr2++;
				if(nr<1000)
					r[nr]=i;
				nr++;
			}
		}
		hb-=b[i];
		hb+=b[i+n];
	}
}
int main()
{
	freopen ("strmatch.in","r",stdin);
	freopen ("strmatch.out","w",stdout);
	gets (a);
	gets (b);
	n=strlen (a);
	m=strlen (b);
	if(n>m){
		puts ("0");
		return 0;
	}
	bston[0]=1;
	for(int i=1;i<=n+1;i++)
		bston[i]=(bston[i-1]*bs)%md;
	rabinkarp();
	printf ("%d\n",nr);
	for(int i=0;i<nr&&i<1000;i++)
		printf ("%d ",r[i]);
//	fprintf (stderr,"%d %d",nr1,nr2);
	return 0;
}