Pagini recente » Cod sursa (job #2234985) | Cod sursa (job #277772) | Cod sursa (job #2325545) | Cod sursa (job #241748) | Cod sursa (job #681187)
Cod sursa(job #681187)
#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;
}