code

Forward Nondeterministic DAWG Matching

The Forward Nondeterministic DAWG Matching algorithm
fndm.c
#define neg(K) (~K)

int search(unsigned char *x, int m, unsigned char *y, int n) {
   unsigned int D, B[SIGMA], NEG0, NEG0m1;
   int i,j,k,count, first;
   if (m>32) return search_large(x,m,y,n);

   /* Preprocessing */
   for (i=0; i<SIGMA; i++) B[i] = neg(0);
   for (j=0; j<m; j++) B[x[j]] = B[x[j]] & neg((1<<j));
   NEG0 = neg(0);
   NEG0m1 = neg(0)<<(m-1);
   
   /* Searching */
   count = 0;
   i = m-1;
   while( i < n ) {
      D = B[y[i]];
      while (D != NEG0) {
         if (D < NEG0m1) {
            k = 0; first=i-m+1;
            while(k<m && x[k]==y[first+k]) k++;
            if (k==m && i<n) count++;
         }
         i = i+1;
         D = (D<<1) | B[y[i]];
      }
      i=i+m;
   }
   return count;
}

/*
 * Forward Nondeterministic DAWG Matching algorithm 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) {
   unsigned int D, B[SIGMA], NEG0, NEG0m1;
   int i,j,k,count, first, p_len;

   p_len = m;
   m = 32;

   /* Preprocessing */
   for (i=0; i<SIGMA; i++) B[i] = neg(0);
   for (j=0; j<m; j++) B[x[j]] = B[x[j]] & neg((1<<j));
   NEG0 = neg(0);
   NEG0m1 = neg(0)<<(m-1);
   
   /* searching */
   count = 0;
   i = m-1;
   while( i < n ) {
      D = B[y[i]];
      while (D != NEG0) {
         if (D < NEG0m1) {
            k = 0; first=i-m+1;
            while(k<p_len && x[k]==y[first+k]) k++;
            if (k==p_len && i<n) count++;
         }
         i = i+1;
         D = (D<<1) | B[y[i]];
      }
      i=i+m;
   }
   return count;
}