Cod sursa(job #147421)

Utilizator the1dragonIonita Alexandru the1dragon Data 2 martie 2008 21:29:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 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 r=0, kM1=M[0], kS1=S[0],kM2=M[0], kS2=S[0], lenS, lenM, i, P1=1, P2=1;
	lenS=strlen(S);
	lenM=strlen(M);
	
	for (i=1; i<lenM; i++)
	{
		kM1=(kM1*b+M[i])%MOD;
		kM2=(kM2*b+M[i])%MOD2;
		kS1=(kS1*b+S[i])%MOD;
		kS2=(kS2*b+S[i])%MOD2;
		P1=(P1*b)%MOD;
		P2=(P2*b)%MOD2;
	}
	//printf("%d %d   %d %d\n", kM1, kS1, kM2, kS2);
	
	if ((kM1==kS1)&&(kM2==kS2))
	{
		++r;
		sol[r]=0;
	}
	for (i=lenM; i<lenS; i++)
	{
		kS1=((kS1- (S[i-lenM]*P1)%MOD + MOD )  *b+S[i])%MOD;
		kS2=((kS2- (S[i-lenM]*P2)%MOD2+ MOD2)  *b+S[i])%MOD2;
	
	//	printf("%d %d   %d %d\n", kM1, kS1, kM2, kS2);
		
		if ((kM1==kS1)&&(kM2==kS2))
		{
			++r;
			if (r<=1001)
				sol[r]=i-lenM+1;
		}
	}
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, 128, 100007, 100021);
	printf("%d\n", r);
	for (i=1; i<=r && i<=1000; i++)
	{
		printf("%d ", sol[i]);
	}
	fclose(stdout);
	return 0;
}