Cod sursa(job #695241)

Utilizator Marius96Marius Gavrilescu Marius96 Data 28 februarie 2012 11:25:53
Problema Potrivirea sirurilor Scor 26
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<cstdio>
#include<cstring>
char a[2000005],b[2000005];
int r[1005],nr;
int lg=0;
//highly idiotic hash follows
struct hash
{
	int v;
	hash (char * s){
		v=0;
		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)
	{
		v-=x;
	}
	void operator+=(int x)
	{
		v+=x;
	}
};

void rabinkarp()
{
	hash ha (a),hb (b);
	for(int i=0;i<strlen (b)-strlen (a)+1;i++){
		if(ha==hb&&(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;
}