Cod sursa(job #402877)

Utilizator BooZZySandu Bogdan BooZZy Data 24 februarie 2010 11:24:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<stdio.h>
#include<string.h>
#define p 73
#define mod1 100007
#define mod2 100021
char sb[2000010],s[2000010];
int h1sb,h2sb,h1s,h2s,n,nb,i,q,nr,v[1010],p1=1,p2=1;
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s %s",&sb,&s);
	nb=strlen(sb);
	n=strlen(s);
	if(nb>n)
	{	
		printf("0\n");
		return 0;
	}
	for(i=0;i<nb;i++)
	{
		h1sb=(h1sb*p+sb[i])%mod1;
		h2sb=(h2sb*p+sb[i])%mod2;
		if(i)
		{
			p1=(p1*p)%mod1;
			p2=(p2*p)%mod2;
		}
	}
	for(i=0;i<n;i++)
	{
		if(i<nb)
		{
			h1s=(h1s*p+s[i])%mod1;
			h2s=(h2s*p+s[i])%mod2;
		}
		else
		{
			h1s=((h1s-(s[i-nb]*p1)%mod1+mod1)*p+s[i])%mod1;
			h2s=((h2s-(s[i-nb]*p2)%mod2+mod2)*p+s[i])%mod2;
		}
		if(h1sb==h1s&&h2sb==h2s)
		{
			nr++;
			if(q<1000)
			v[q++]=i-nb+1;
		}
	}
	printf("%d\n",nr);
	for(i=0;i<q;i++)
		printf("%d ",v[i]);
	return 0;
}