Cod sursa(job #428276)

Utilizator Andrei_ScorpioAndreiana Andrei Daniel Andrei_Scorpio Data 29 martie 2010 08:54:41
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<stdio.h>
#include<string.h>
#define p 101
#define m1 996067
#define m2 999983
#define Nmax 2000010
char a[Nmax],b[Nmax];
int n1,n2,ha1,ha2,hb1,hb2,pmax1,pmax2,nr,sol[1005];

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*p+a[i])%m1;	
	ha2=(ha2*p+a[i])%m2;	
	hb1=(hb1*p+b[i])%m1;	
	hb2=(hb2*p+b[i])%m2;
	if(i!=0){
		pmax1=(pmax1*p)%m1;
		pmax2=(pmax2*p)%m2;}
	}
	if(ha1==hb1 && ha2==hb2)
		sol[nr++]=0;
	for(i=n1;i<n2;i++)
	{
		hb1=((hb1-b[i-n1]*pmax1)*p+b[i])%m1;
		hb2=((hb2-b[i-n1]*pmax2)*p+b[i])%m2;
		if(ha1==hb1 && ha2==hb2)
			sol[nr++]=i-n1+1;
		if(nr==1000)
			break;
	}
	printf("%d\n",nr);
	for(i=0;i<nr;i++)
		printf("%d ",sol[i]);
	return 0;
}