code

Backward Nondeterministic DAWG Matching

The Backward Nondeterministic DAWG Matching algorithm
bndm.c

int search(unsigned char *x, int m, unsigned char *y, int n) {
   int B[SIGMA];
   int i, j, s, D, last, count;

   if (m > 32) return search_large(x,m,y,n);

   /* Preprocessing */
   for (i=0; i<SIGMA; i++) B[i]=0;
   s=1;
   for (i=m-1; i>=0; i--) {
      B[x[i]] |= s;
      s <<= 1;
   }

   /* Searching */
   j=0; count=0;
   while (j <= n-m) {
      i=m-1; last=m;
      D = ~0;
      while (i>=0 && D!=0) {
         D &= B[y[j+i]];
         i--;
         if (D != 0) {
            if (i >= 0) last = i+1;
            else count ++;
         }
         D <<= 1;
      }
      j += last;
   }
   return count;
  }

/*
 * Backward Nondeterministic DAWG Matching designed for large patterns
 * The present implementation searches for prefixes of the pattern of length 32.
 * When an occurrence is found the algorithm tests for the whole occurrence of the pattern
 */


int search_large(unsigned char *x, int m, unsigned char *y, int n) {
   int B[SIGMA];
   int i, j, s, D, last, count, p_len, k;

   p_len = m;
   m = 32;

   /* Preprocessing */
   memset(B,0,SIGMA*sizeof(int));
   s=1;
   for (i=m-1; i>=0; i--) {
      B[x[i]] |= s;
      s <<= 1;
   }

   /* Searching */
   j=0; count=0;
   while (j <= n-m) {
      i=m-1; last=m;
      D = ~0;
      while (i>=0 && D!=0) {
         D &= B[y[j+i]];
         i--;
         if (D != 0) {
            if (i >= 0)
               last = i+1;
            else {
               k = m;
               while(k<p_len && x[k]==y[j+k]) k++;            
               if (k==p_len) count ++;
            }
         }
         D <<= 1;
      }
      j += last;
   }
   return count;
}