Pagini recente » Cod sursa (job #3208016) | Cod sursa (job #2604643) | Cod sursa (job #3233540) | Cod sursa (job #3199432) | Cod sursa (job #629710)
Cod sursa(job #629710)
//varianta cu un sg hash...
#include <stdio.h>
#include <string.h>
#define NMAX 2000004
#define MOD1 666013
#define MOD2 100007
#define B 73
char a[NMAX],b[NMAX];
int nna[NMAX],nnb[NMAX],na,nb;
char alfabet[]={"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"};
int rez[1005],indice=0;
int main(){
int i;
FILE *fin=fopen("strmatch.in","r");
FILE *fout=fopen("strmatch.out","w");
fscanf(fin,"%s%s",b,a);
// printf("sirul pattern este: %s\n",b);
na=strlen(a);
nb=strlen(b);
//transform a[] si b[]
// printf("lungimea sirului pattern este %d\n",nb);
for(i=0;i<na;i++){
nna[i]=strchr(alfabet,a[i])-alfabet+1;
//printf("%d ",nna[i]);
}
//printf("\n");
// printf("lungimea sirului pattern este %d\n",nb);
for(i=0;i<nb;i++){
nnb[i]=strchr(alfabet,b[i])-alfabet+1;
//printf("%d ",nnb[i]);
}
// printf("\n");
//practic fiecare nna[] si nnb[] sunt vectori de cifre in baza 26
long long nr1=0,nr2=0,hashb1=0,hashb2=0;
//calculez hash pattern
for(i=0;i<nb;i++){
hashb1=(hashb1*B+nnb[i])%MOD1;
hashb2=(hashb2*B+nnb[i])%MOD2;
}
//printf("hashul patternului este %lld\n",hashb1);
for(i=0;i<nb;i++){
nr1=(nr1*B+nna[i])%MOD1;
nr2=(nr2*B+nna[i])%MOD2;
}
//printf("%lld ",nr);
long long putere1=1,putere2=1;//calc 26^(nb-1)
for(i=1;i<nb;i++){
putere1=(putere1*B)%MOD1;
putere2=(putere2*B)%MOD2;
}
//printf("puterea este %lld\n",putere);
if((nr1==hashb1)&&(nr2==hashb2) ){
rez[indice++]=0;
//printf("0\n");
}
for(i=1;i<=(na-nb);i++){
// fprintf(fout,"%lld %lld\n",nr1,nr2);
nr1=(nr1-(putere1*nna[i-1])%MOD1+MOD1)%MOD1;
nr1=(nr1*B+nna[i+nb-1])%MOD1;
nr2=(nr2-(putere2*nna[i-1])%MOD2+MOD2)%MOD2;
nr2=(nr2*B+nna[i+nb-1])%MOD2;
//printf("%lld ",nr);
if((nr1==hashb1)&&(nr2==hashb2)){
rez[indice++]=i;
if(indice==1000)break;
//printf("%d\n",i);
}
}
fprintf(fout,"%d\n",indice);
for(i=0;i<indice;i++)
fprintf(fout,"%d ",rez[i]);
//printf("%s %s\n",a,b);
return 0;
}