Cod sursa(job #428712)

Utilizator Andrei_ScorpioAndreiana Andrei Daniel Andrei_Scorpio Data 29 martie 2010 14:57:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<stdio.h>
#include<string.h>

#define p1 41 // pentru primul hash
#define p2 73 // pentru al doilea hash

#define Nmax 2000010
char a[Nmax],b[Nmax];
int n1,n2,ha1,ha2,hb1,hb2,pmax1,pmax2,nr,sol[Nmax];

int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
    gets(a);
    gets(b);
	n1=strlen(a);
	n2=strlen(b);
	if(n1>n2)	{printf("0\n");return 0;}
	pmax1=pmax2=1;
	int i;
	for(i=0;i<n1;i++)
	{
		ha1=ha1*p1+a[i];	
		ha2=ha2*p2+a[i];	
		hb1=hb1*p1+b[i];	
		hb2=hb2*p2+b[i];
		if(i!=0)
		{
			pmax1=pmax1*p1;
			pmax2=pmax2*p2;
		}
	}
	if(ha1==hb1 && ha2==hb2)
		sol[nr++]=0;
	for(i=n1;i<n2;i++)
	{
		hb1=((hb1-(b[i-n1]*pmax1))*p1+b[i]);
		hb2=((hb2-(b[i-n1]*pmax2))*p2+b[i]);
	
		if(ha1==hb1 && ha2==hb2)
			sol[nr++]=i-n1+1;
	}
	printf("%d\n",nr);
	for(i=0;i<nr && i<1000;i++)
		printf("%d ",sol[i]);
	return 0;
}