code

Linear DAWG Matching

The Linear DAWG Matching algorithm
ldm.c
#include "include/AUTOMATON.h"

int search(unsigned char *x, int m, unsigned char *y, int n) {
   int k, R, L, r, ell, end, count;
   int *ttrans, *tlength, *tsuffix;
   int *ttransSMA;
   char *tterminal;
   unsigned char *xR;
 
   count = 0;
   /* Preprocessing */
   xR = reverse(x,m);
   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(xR, m, ttrans, tlength, tsuffix, tterminal);

   ttransSMA = (int *)malloc((m+1)*SIGMA*sizeof(int));
   memset(ttransSMA, -1, (m+1)*SIGMA*sizeof(int));
   preSMA(x, m, ttransSMA);
   end = n/m;
   if (n%m > 0) ++end;

   /* Searching */
   for (k = 1; k < end; ++k) {
      R = L = r = ell = 0;
      while (L != UNDEFINED && k*m-1-ell >= 0) {
         L = getTarget(L, y[k*m-1-ell]);
         ++ell;
         if (L != UNDEFINED && isTerminal(L))
            R = ell;
      }
      while (R > r-k*m) {
         if (R == m) OUTPUT(k*m+r-m);
         ++r;
         if (r == m) break;
         R = getSMA(R, y[k*m-1+r]);
      }
   }
   for (k = (end-1)*m; k <= n - m; ++k) {
      for (r = 0; r < m && x[r] == y[r + k]; ++r);
      if (r >= m) count++;
   }
   free(ttrans);
   free(tlength);
   free(tsuffix);
   free(ttransSMA);
   free(tterminal);
   return count;
}