Cod sursa(job #681187)

Utilizator an_drey_curentandreycurent an_drey_curent Data 16 februarie 2012 19:12:33
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<stdio.h>
#include<string.h>
#define BAZA 128
#define MAX 2000005
#define PRIM1 123457
#define PRIM2 666013
char A[MAX],B[MAX];
int LA,LB,hashA1=0,hashA2=0,POW1,POW2;
int POTRIVIRI[BAZA*10],contor=0;
void citire()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	scanf("%s",&A);LA=strlen(A)-1;
	scanf("%s",&B);LB=strlen(B)-1;
}
void calcul()
{
	POW1=1,POW2=1;
	for(int i=0;i<LA;i++)
	{
		POW1=(POW1*BAZA)%PRIM1;
		POW2=(POW2*BAZA)%PRIM2;
	}
}
void rabin_karp()
{
	int i=0,hashB1=0,hashB2=0;
	for(i=0;i<=LA;i++)
	{
		hashB1=(hashB1*BAZA+B[i])%PRIM1;
		hashA1=(hashA1*BAZA+A[i])%PRIM1;
		hashB2=(hashB2*BAZA+B[i])%PRIM2;
		hashA2=(hashA2*BAZA+A[i])%PRIM2;
	}
	if( (hashB1==hashA1) && (hashB2==hashA2) )
		POTRIVIRI[++contor]=0;
	calcul();
	for(i=LA+1;i<=LB;i++)
	{
		hashB1=( (hashB1- (B[i-LA-1]*POW1%PRIM1) +PRIM1) *BAZA+B[i] )%PRIM1;
		hashB2=( (hashB2- (B[i-LA-1]*POW2%PRIM2) +PRIM2) *BAZA+B[i] )%PRIM2;
		if( (hashB1==hashA1) && (hashB2==hashA2) )
		{
			POTRIVIRI[++contor]=i-LA;
			if(contor==1000)
				break;
		}
	}
}
void afisare()
{
	printf("%d\n",contor);
	for(int i=1;i<=contor;i++)
		printf("%d ",POTRIVIRI[i]);
}
int main()
{
	citire();
	rabin_karp();
	afisare();
	return 0;
}