code

Backward Nondeterministic DAWG Matching for long patterns

The Backward Nondeterministic DAWG Matching for long patterns algorithm
lbndm.c

int verify(unsigned char *y, int left, unsigned char *x, int m, int k) {
   int j,i;
   int count = 0;
   for (j=0; j<k; j++) {
      if (m+j > left) break;
      i = 0;
      while(i<m && y[i]==x[i]) i++;
      if (i>=m) count++;
      y++;
   }
   return count;
}

int search(unsigned char *x, int m, unsigned char *y, int n)
{
   unsigned int B[SIGMA] = {0};
   unsigned int M;
   int k;
   int i, j, l;
   int m1, m2, rmd;

   /* Preprocessing */
   M = 1 << (WORD-1);
   k = (m-1)/WORD+1;
   m1 = m-1;
   m2 = m1-k;
   rmd = m-(m/k)*k;
   for (i=m/k, l=m; i>0; i--, l-=k)
      for (j=k; j>0; j--)
         B[x[l-j]] |= 1 << (WORD-i);

   /* Searching */
   int count = 0;
   j = 0;
   while (j <= n-m) {
      unsigned int D = B[y[j+m1]];
      int last = (D & M) ? m-k-rmd : m-rmd;
      l = m2;
      while (D) {
         D = (D << 1) & B[y[j+l]];
         if (D & M) {
            if (l < k+rmd) {
               count += verify(y+j, n-j, x, m, k);
               break;
            }
            last = l-(k+rmd)+1;
         }
         l -= k;
      }
      j += last;
   }
   return count;
}