Cod sursa(job #155029)

Utilizator mihai0110Bivol Mihai mihai0110 Data 11 martie 2008 17:52:02
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<stdio.h>
#include<string.h>
#define B 73
#define mod1 100021
#define mod2 100007

long n1,n2,m1,m2,i,p1,p2,la,lb,nr;
long sol[1001];
char a[2000000],b[2000000];

int main(void)
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s%s",a,b);
	p1=1;
	p2=1;
	la=strlen(a);
	lb=strlen(b);
	for(i=0;i<la;i++)
	{
		n1=(n1*B+a[i])%mod1;
		n2=(n2*B+a[i])%mod2;
		if(i)
		{
		p1*=B;
		p2*=B;
		}
	}
	if(la>lb)
	return 0;
	for(i=0;i<la;i++)
	{
		m1=(m1*B+b[i])%mod1;
		m2=(m2*B+b[i])%mod2;
	}
	if(m1==n1&&m2==n2)
	sol[++nr]=0;
	for(i=la;i<lb;i++)
	{
		m1=((m1-(b[i-la]*p1)%mod1+mod1)*B+b[i])%mod1;
		m2=((m2-(b[i-la]*p2)%mod2+mod2)*B+b[i])%mod2;
		if(m1==n1&&m2==n2)
		{
			nr++;
			if(nr<=1000)
			sol[nr]=i-la+1;
		}
	}
	printf("%ld\n",nr);
	for(i=1;i<=nr;i++)
	printf("%ld ",sol[i]);
	printf("\n");
	return 0;
}