Cod sursa(job #381562)

Utilizator allynaAlina S allyna Data 10 ianuarie 2010 22:18:32
Problema Potrivirea sirurilor Scor 100
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 100021
char a[MAXN],b[MAXN];
int m,n,hasha1,hasha2,p1,p2,hash1,hash2,num;
char v[MAXN];
int main()
{
	freopen("strmatch.in", "rt", stdin);
	freopen("strmatch.out", "wt", stdout);
	scanf("%s %s",a,b);
	n=strlen(a);
	m=strlen(b);
	p1=p2=1;hasha1=hasha2=0;
	for (int i=0;i<n;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 (n>m)
	{
		printf("0\n");
		return 0;
	}
	for (int i=0;i<n;i++)
		hash1=(hash1*P+b[i])%MOD1,hash2=(hash2*P+b[i])%MOD2;
	if (hash1==hasha1&&hash2==hasha2)
		v[0]=1,num++;
	for (int i=n;i<m;i++)
	{
		hash1=((hash1-(b[i-n]*p1)%MOD1+MOD1)*P+b[i])%MOD1,hash2=((hash2-(b[i-n]*p2)%MOD2+MOD2)*P+b[i])%MOD2;
		if (hash1==hasha1 && hash2==hasha2)
			v[i-n+1]=1,num++;
	}
	printf("%d\n",num);
	num=0;
	for (int i=0;i<m && num<1000;i++)
		if (v[i])
			num++,printf("%d ",i);
	printf("\n");
	return 0;
}