Cod sursa(job #825148)

Utilizator BalcauIonutFMI-Balcau Ionut BalcauIonut Data 27 noiembrie 2012 17:22:55
Problema Potrivirea sirurilor Scor 2
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<cstdio>
#include<cstring>
#define MAXN 2000001
#define MOD 666013
#define p 73

char a[MAXN],s[MAXN];

int	pp=1,n,m,ha,hs,match[1001]; 

int main(){
	
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	gets(a); gets(s);
	n=strlen(a); m=strlen(s);
	if(n>m){
		printf("%d",0);
	}
	//calc hash a
	ha=0; int i;
	for(i=0;i<n;++i){
		ha=(ha*p+a[i])%MOD;
		if(i!=0) pp=pp*p%MOD;
	}
	//rolling hash pe s
	//hash de primele n
	hs=0;
	for(i=0;i<n;++i)
		hs=(hs*p+s[i])%MOD;
	
	int nr=0;
	if(hs==ha){nr=1; match[1]=0;}
	//rolling hash

	for(i=n;i<m;++i){
		hs=((hs-(s[i-n]*pp)%MOD)*p+s[i])%MOD;
		if(ha==hs){
			nr++;
			if(nr<=1000) match[nr]=i-n+1;
		}
	}
	printf("%d\n",nr);
	for(i=1;i<=nr && i<=1000; ++i)
		printf("%d ",match[i]);
	return 0;
}