Cod sursa(job #512294)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 13 decembrie 2010 19:38:02
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <cstdio>
#include <cstring>
#define p 73
#define mod 666013
#define nmax 2000010

int na, nb, hasha, hash, nr, sol[nmax];
char a[nmax], b[nmax];


int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s %s",&a,&b);
	na=strlen(a);
	nb=strlen(b);
	if (na>nb)
	{
		printf("0\n");
		return 0;
	}
	int hasha=0, hash=0;
	int i, pn=1;
	for (i=0; i<na; i++)
	{
		hasha=(hasha*p+a[i])%mod;
		if (i>0) pn=(pn*p)%mod;
		hash=(hash*p+b[i])%mod;
	}
	if (hasha==hash) sol[++nr]=1;
	for (i=na; i<nb; i++)
	{
		hash=((hash-(b[i-na]*pn)%mod +mod)*p+b[i])%mod;
		if (hash==hasha) sol[++nr]=i-na+1;
	}
	printf("%d\n",nr);
	if (nr>1000) nr=1000;
	for (i=1; i<=nr; i++) printf("%d ",sol[i]);
}