Cod sursa(job #236707)

Utilizator luk17Luca Bogdan luk17 Data 28 decembrie 2008 12:27:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<stdio.h>
#include<string.h>
#define NMAX 2000001
#define baza 73
#define mod1 1000007
#define mod2 1000023

char a[NMAX],b[NMAX];
long n,m,hasha1,hasha2,hashb1,hashb2,lung;
int viz[NMAX];
int main()
{
	long i;
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s",a);
	scanf("%s",b);
	m=strlen(a);
	n=strlen(b);
	hasha1=hasha2=hashb1=hashb2=0;
	long d1,d2;
	d1=d2=1;
	for(i=0;i<m;i++)
	{
		hasha1=(hasha1*baza+a[i])%mod1;
		hasha2=(hasha2*baza+a[i])%mod2;
		hashb1=(hashb1*baza+b[i])%mod1;
		hashb2=(hashb2*baza+b[i])%mod2;
		if(i!=0)
		{
			d1=(d1*baza)%mod1;
			d2=(d2*baza)%mod2;
		}
	}
	if(hasha1==hashb1&&hasha2==hashb2)
	{viz[0]=1;
	lung++;
	}
	for(i=1;i<=n-m+1;i++)
	{
		hashb1=((hashb1-(b[i-1]*d1)%mod1+mod1)*baza+b[i+m-1])%mod1;
		hashb2=((hashb2-(b[i-1]*d2)%mod2+mod2)*baza+b[i+m-1])%mod2;
		if(hasha1==hashb1&&hasha2==hashb2)
		{
			lung++;viz[i]=1;
		}
	}
	printf("%ld\n",lung);
	int contor=1;
	for(i=0;i<n&&contor<=1000;i++)
		if(viz[i]==1)
		{
			printf("%ld ",i);
			contor++;
		}
	return 0;
}