code

Forward Simplified Backward Nondeterministic DAWG Matching

The Forward Simplified Backward Nondeterministic DAWG Matching algorithm
fsbndm.c

int search(unsigned char *x, int m, unsigned char *y, int n) {
   unsigned int B[SIGMA], D, set;
   int i, j, pos, mMinus1, count;
   
   if (m>31) return search_large(x,m,y,n);

   /* Preprocessing */
   count = 0;
   mMinus1 = m - 1;
   set = 1;
   for (i=0; i<SIGMA; i++) B[i]=set;
   for (i = 0; i < m; ++i) B[x[i]] |= (1<<(m-i));

   /* Searching */
   if (!memcmp(x,y,m)) OUTPUT(0);
   j = m;
   while (j < n) {
      D = (B[y[j+1]]<<1) & B[y[j]];
      if (D != 0) {
         pos = j;
         while (D=(D<<1) & B[y[j-1]]) --j;
         j += mMinus1;
         if (j == pos) {
            OUTPUT(j);
            ++j;
         }
      }
      else j+=m;
   }
   return count;
}

/*
 * Forward Semplified BNDM 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 B[SIGMA], D, set;
   int i, j, pos, mMinus1, count, p_len, k,s;
   
   p_len = m;
   m = 30;

   /* Preprocessing */
   count = 0;
   mMinus1 = m - 1;
   set = 1;
   for (i=0; i<SIGMA; i++) B[i]=set;
   for (i = 0; i < m; ++i) B[x[i]] |= (1<<(m-i));

   /* Searching */
   if (!memcmp(x,y,m)) OUTPUT(0);
   j = m;
   while (j < n) {
      D = (B[y[j+1]]<<1) & B[y[j]];
      if (D != 0) {
         pos = j;
         while (D=(D<<1) & B[y[j-1]]) --j;
         j += mMinus1;
         if (j == pos) {
            k = m; s=j-mMinus1;
            while (k<p_len && x[k]==y[s+k]) k++;
            if (k==p_len) OUTPUT(s);
            ++j;
         }
      }
      else j+=m;
   }
   return count;
}