code

Forward DAWG Matching

The Forward DAWG Matching algorithm
fdm.c
#include "include/AUTOMATON.h"

int search(unsigned char *x, int m, unsigned char *y, int n) {
   int j, init, ell, state, count;
   int *ttrans, *tlength, *tsuffix;
   unsigned char *tterminal;
 
   count = 0;
   /* Preprocessing */
   ttrans = (int *)malloc(3*m*SIGMA*sizeof(int));
   memset(ttrans, -1, 3*m*SIGMA*sizeof(int));
   tlength = (int *)calloc(3*m, sizeof(int));
   tsuffix = (int *)calloc(3*m, sizeof(int));
   tterminal = (char *)calloc(3*m, sizeof(char));
   buildSimpleSuffixAutomaton(x, m, ttrans, tlength, tsuffix, tterminal);
   init = 0;
 
   /* Searching */
   ell = 0;
   state = init;
   for (j = 0; j < n; ++j) {
      if (getTarget(state, y[j]) != UNDEFINED) {
         ++ell;
         state = getTarget(state, y[j]);
      }
      else {
         while (state != init && getTarget(state, y[j]) == UNDEFINED)
            state = getSuffixLink(state);
         if (getTarget(state, y[j]) != UNDEFINED) {
            ell = getLength(state) + 1;
            state = getTarget(state, y[j]);
         }
         else {
            ell = 0;
            state = init;
         }
      }
      if (ell == m)
         OUTPUT(j - m + 1);
   }
   free(ttrans);
   free(tlength);
   free(tsuffix);
   free(tterminal);
   return count;
}