Cod sursa(job #381543)

Utilizator allynaAlina S allyna Data 10 ianuarie 2010 21:18:05
Problema Potrivirea sirurilor Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <stdio.h>
#include <string.h>
#define MAXN 2000001
#define P 73
#define MOD1 100007
#define MOD2 100019
char p[MAXN],t[MAXN],n,m,v[MAXN];
int hashp,q,num,hash1,hash2,i,q1,q2;
int main()
{
	freopen("strmatch.in", "rt", stdin);
	freopen("strmatch.out", "wt", stdout);
	scanf("%s %s",p,t);
	n=strlen(p);
	m=strlen(t);
	q1=q2=1;
	int hashp1=0,hashp2=0;
	for (i=0;i<n;i++)
		hashp1=(hashp1*P+p[i])%MOD1,
		hashp2=(hashp2*P+p[i])%MOD2;		
		if (i!=0)
			q1=(q1*P)%MOD1,q2=(q2*P)%MOD2;
	if (n>m)
	{
		printf("0\n");
		return 0;
	}
	for (i=0;i<n;i++)
		hash1=(hash1*P+t[i])%MOD1,hash2=(hash1*P+t[i])%MOD2;
	if (hash1==hashp1 && hash2==hashp2)
		v[0]=1, num++;
	for (i=n;i<m;i++)
	{
		hash1=((hash1-(t[i-n]*q1)%MOD1+MOD1)*P+t[i])%MOD1,
        hash2=((hash1-(t[i-n]*q2)%MOD2+MOD2)*P+t[i])%MOD2;
		if (hash1==hashp1&&hash2==hashp2)
			v[i-n+1]=1,num++;
	}
	printf("%d\n",num);
	num=0;
	for (i=0;i<m && num<1000;i++)
		if (v[i])
			num++,
			printf("%d ",i);
	printf("\n");
	return 0;
}