Cod sursa(job #425660)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 25 martie 2010 22:16:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <stdio.h>
#define NMAX 2000005
#define P 73
#define MOD1 100007
#define MOD2 100021
#define LMAX 1005
char A[NMAX],B[NMAX];
int n,m,hash1,hash2,P1,P2,match[LMAX],r;
inline int ok(char x)
{
	return (x>='A' && x<='Z') || (x>='a' && x<='z') || (x>='0' && x<='9');
}
int hash3,hash4;
int main()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	fgets(A+1,NMAX,stdin);
	fgets(B+1,NMAX,stdin);
	while (ok(A[n+1]))
		n++;
	while (ok(B[m+1]))
		m++;
	int i;
	P1=P2=1;
	for (i=1; i<=n; i++)
	{
		hash1=(hash1*P+A[i])%MOD1;
		hash2=(hash2*P+A[i])%MOD2;
		if (i!=1)
			P1=(P1*P)%MOD1,P2=(P2*P)%MOD2;
	}
	for (i=1; i<=n; i++)
	{
		hash3=(hash3*P+B[i])%MOD1;
		hash4=(hash4*P+B[i])%MOD2;
	}
	if (hash1==hash3 && hash2==hash4)
		match[++r]=0;
	for (i=n+1; i<=m; i++)
	{
		hash3=((hash3-(B[i-n]*P1)%MOD1+MOD1)*P+B[i]) % MOD1;
		hash4=((hash4-(B[i-n]*P2)%MOD2+MOD2)*P+B[i]) % MOD2;
		if (hash1==hash3 && hash2==hash4)
		{
			r++;
			if (r<=1000)
				match[r]=i-n;
		}
	}
	printf("%d\n",r);
	for (i=1; i<=r && i<=1000; i++)
		printf("%d ",match[i]);
	printf("\n");
	return 0;
}