Cod sursa(job #312413)

Utilizator cotofanaCotofana Cristian cotofana Data 5 mai 2009 21:42:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <stdio.h>
#include <string.h>
#define dim 2000010
#define p 73
#define mod1 100007
#define mod2 100021

char a[dim], b[dim], match[dim];
int hasha1, hasha2, hash1, hash2, na, nb, ct=0, p1, p2;

int main()
{
	int i;
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	scanf("%s %s\n", a, b);
	na=strlen(a);
	nb=strlen(b);
	
	hasha1=hasha2=0;
	p1=p2=1;
	for (i=0; i<na; i++)
	{
		hasha1=(hasha1*p+a[i])%mod1;
		hasha2=(hasha2*p+a[i])%mod2;
		
		if (i!=0)
		{
			p1=(p1*p)%mod1;
			p2=(p2*p)%mod2;
		}
	}
	
	if (na>nb)
	{
		printf("0\n");
		return 0;
	}
	
	hash1=hash2=0;
	for (i=0; i<na; i++)
	{
		hash1=(hash1*p+b[i])%mod1;
		hash2=(hash2*p+b[i])%mod2;
	}
	
	if (hash1==hasha1 && hash2==hasha2)
	{
		match[0]=1;
		ct++;
	}
	
	for (i=na; i<nb; i++)
	{
		hash1=((hash1-(b[i-na]*p1)%mod1+mod1)*p+b[i])%mod1;
		hash2=((hash2-(b[i-na]*p2)%mod2+mod2)*p+b[i])%mod2;
		
		if (hash1==hasha1 && hash2==hasha2)
		{
			match[i-na+1]=1;
			ct++;
		}
	}
	
	printf("%d\n", ct);
	
	ct=0;
	for (i=0; i<nb && ct<1000; i++)
		if (match[i])
		{
			printf("%d ", i);
			ct++;
		}
	printf("\n");
	
	return 0;
}