Cod sursa(job #432081)

Utilizator za_wolfpalianos cristian za_wolf Data 1 aprilie 2010 20:02:59
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
//#include "stdafx.h"
#include<stdio.h>
#include<string.h>
#define NMAX 2000010
#define p 73
#define mod1 100007
#define mod2 100021
char x[NMAX],y[NMAX];
int n,m,p1,p2,i,j,rez[NMAX],hashx1,hashx2,hashy1,hashy2;
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s %s",x,y);
	n=strlen(x)-1;
	m=strlen(y)-1;
	if (n>m)
	{
		printf("0\n");
		return 0;
	}
	p1=p2=1;
	for (i=0;i<=n;i++)
	{
		hashx1=(hashx1*p+x[i])% mod1;
		hashx2=(hashx2*p+x[i])% mod2;
		if (i!=0)
		{
			p1=(p1*p)%mod1;
			p2=(p2*p)%mod2;
		}
	}
	for (i=0;i<=n;i++)
	{
		hashy1=(hashy1*p+y[i])%mod1;
		hashy2=(hashy2*p+y[i])%mod2;
	}
	if (hashx1==hashy1 && hashx2==hashy2)
		rez[++rez[0]]=1;

	for (i=n+1;i<=m;i++)
	{
		hashy1=((hashy1-(y[i-n-1]*p1)%mod1+mod1)*p+y[i])%mod1;
		hashy2=((hashy2-(y[i-n-1]*p2)%mod2+mod2)*p+y[i])%mod2;
		if (hashx1==hashy1 && hashx2==hashy2)
			rez[++rez[0]]=i-n;
	}
	printf("%d\n",rez[0]);
	if (rez[0]>1000)
		rez[0]=1000;
	for (i=1;i<=rez[0];i++)
			printf("%d ",rez[i]);
	printf("\n");

	return 0;
}