Cod sursa(job #147354)

Utilizator the1dragonIonita Alexandru the1dragon Data 2 martie 2008 20:30:25
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include<stdio.h>
#include<string.h>

char A[2000001], B[2000001];
int sol[1024];

int rabin_karp(char *S, char *M,int b, int MOD, int MOD2, int MOD3)
{
	int r=0, kM=0, kS=0,kM2=0, kS2=0,kM3=0, kS3=0, lenS, lenM, i, K=1, K2=1, K3=1;
	lenS=strlen(S);
	lenM=strlen(M);
	for (i=0; i<lenM; i++)
	{
		K*=b;		K2*=b;		K3*=b;
		K%=MOD;		K2%=MOD2;	K3%=MOD3;
		
		kM*=b;		kM2*=b;		kM3*=b;
		kM+=M[i];	kM2+=M[i];  kM3+=M[i];
		kM%=MOD;	kM2%=MOD2;	kM3%=MOD3;
		kS*=b;		kS2*=b;		kS3*=b;
		kS+=S[i];	kS2+=S[i];	kS3+=S[i];
		kS%=MOD;	kS2%=MOD2;	kS3%=MOD3;
	}
	if ((kS2==kM2)&&(kS2==kM2)&&(kS3==kM3))
	{
			++r;
			sol[r]=0;
	}
//	printf("%d %d   %d %d   %d %d\n", kM, kS, kM2, kS2, kM3, kS3);
	
	for (; i<lenS; i++)
	{
		kS*=b;		kS2*=b;		kS3*=b;
		kS-=(S[i-lenM]*K)%MOD;
		kS2-=(S[i-lenM]*K2)%MOD2;
		kS3-=(S[i-lenM]*K3)%MOD3;
		
		kS+=S[i];	kS2+=S[i];	kS3+=S[i];
		kS%=MOD;	kS2%=MOD2;	kS3%=MOD3;
		if ((kS==kM)&&(kS2==kM2)&&(kS3==kM3))
		{
			++r;
			sol[r]=i-lenM+1;
		}
//		printf("%d %d   %d %d   %d %d\n", kM, kS, kM2, kS2, kM3, kS3);
	
	}
	return r;
}


int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	gets(A);
	gets(B);
	int r, i;
	r=rabin_karp(B, A, 256, 20347, 20321, 69);
	printf("%d\n", r);
	for (i=1; i<=r && i<=1000; i++)
	{
		printf("%d ", sol[i]);
	}
	fclose(stdout);
	return 0;
}