FANDOM


   /* Preprocessing of the Bad Character function shift. */
   PRE_BC(char *x, int m, int bm_bc[]) {
    int a, j;
   
    for (a=0; a < ASIZE; a++) bm_bc[a]=m;
    for (j=0; j < m-1; j++) bm_bc[x[j]]=m-j-1;
   }
   
   
   /* Preprocessing of the Good Suffix function shift. */
   PRE_GS(char *x, int m, int bm_gs[]) {
    int i, j, p, f[XSIZE];
   
    memset(bm_gs, 0, (m+1)*sizeof(int));
    f[m]=j=m+1;
    for (i=m; i > 0; i--) {
       while (j <= m && x[i-1] != x[j-1]) {
          if (bm_gs[j] == 0) bm_gs[j]=j-i;
          j=f[j];
       }
       f[i-1]=--j;
    }
    p=f[0];
    for (j=0; j <= m; ++j) {
       if (bm_gs[j] == 0) bm_gs[j]=p;
       if (j == p) p=f[p];
    }
   }
   
   
   /* Boyer-Moore string matching algorithm. */
   void BM(char *y, char *x, int n, int m) {
    int i, j, bm_gs[XSIZE], bm_bc[ASIZE];
   
    /* Preprocessing */
    PRE_GS(x, m, bm_gs);
    PRE_BC(x, m, bm_bc);
   
    i=0;
    while(i <= n-m) {
      for (j=m-1; j >= 0 && y[i+j]==x[j]; --j);
      if (j < 0){
        OUTPUT(i);
        i+=bm_gs[j+1];
      }
      else {
        i+=MAX(bm_gs[j+1],bm_bc[y[i+j]]-m+j+1);
      }   
    }
   }

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.