code

Two-Way Nondeterministic DAWG Matching

The Two-Way Nondeterministic DAWG Matching algorithm
tndma.c

int search(unsigned char *x, int m, unsigned char *y, int n) {
   int i,j,s,last, restore[XSIZE+1];
   unsigned int d, B[SIGMA];
   int count = 0;
   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;
   }
   last = m;
   s = (unsigned int)(~0) >> (WORD-m);
   for (i=m-1; i>=0; i--) {
      s &= B[x[i]]; 
      if (s & ((unsigned int)1<<(m-1))) {
         if (i > 0)  last = i; 
      }
      restore[m-i] = last;
      s <<= 1;
   }

   /* Searching */
   j=m-1;
   while (j < n) {
      i=0;
      last=m;
      d = B[y[j]];
      if ((d&1) == 0) {
         while (d!=0 && !(d&((unsigned int)1<<i))) {
            i++;
            d &= B[y[j+i]]<<i;
         } 
         if (d==0 || j+i>=n ) {
              if (B[y[j+i]]==0) last = i+m;
            goto over;
         } 
         j += i; 
         last = restore[i]; 
      }

      do {
         i++;
         if (d & ((unsigned int)1<<(m-1))) {
            if (i < m)  last = m-i; 
            else {
               OUTPUT(j); 
               goto over;
            } 
         }
         d<<=1;
         d &= B[y[j-i]]; 
      } while(d != 0); 

      over:
      j += last; 
   } 
   return(count);
}

/*
 * Two-Way 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)
{
   int i,j,s,last, restore[XSIZE+1], p_len, k;
   unsigned int D, B[SIGMA];
   int count = 0;
   
   p_len = m;
   m = 32;

   /* 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;
   }
   last = m;
   s = (unsigned int)(~0) >> (WORD-m);
   for (i=m-1; i>=0; i--) {
      s &= B[x[i]]; 
      if (s & ((unsigned int)1<<(m-1))) {
         if (i > 0)  last = i; 
      }
      restore[m-i] = last;
      s <<= 1;
   }

   /* Searching */
   j=m-1;
   while (j < n){
      i=0;
      last=m;
      D = B[y[j]];
      if ((D&1) == 0) {
         while (D!=0 && !(D & ((unsigned int)1<<i))) {
            i++;
            D &= B[y[j+i]]<<i;
         } 
         if (D==0 || j+i>=n ) {
               if (B[y[j+i]]==0) last = i+m; 
            goto over;
         } 
         j += i; 
         last = restore[i]; 
      }

      do {
         i++;
         if (D & ((unsigned int)1<<(m-1))) {
            if (i < m)  last = m-i; 
            else {
               k = m;
               while(k<p_len && x[k]==y[j-m+1+k]) k++;
               if (k>=p_len) OUTPUT(j-m+1); 
               goto over;
            } 
         }
         D<<=1;
         D &= B[y[j-i]]; 
      } while(D != 0); 

      over:
      j += last; 
   } 
   return(count);
}