code

Double Forward DAWG Matching

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

int search(unsigned char *x, int m, unsigned char *y, int n, int a) {
   int init, state1, state2, ell, count;
   int alpha, beta;
   int *ttrans, *tlength, *tsuffix;
   unsigned char *tterminal;
   int i, j, s, end, nMinusM, logM, temp;

   /* 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 */
   count = 0;
   logM = 0;
   temp = m;
   while (temp > a) {
      ++logM;
      temp /= a;
   }
   ++logM;

   beta = m-1-MAX(1,MIN(m/5, 3*logM));
   alpha = MIN(m/2,beta-1);
   s = 0;
   ell = 0;
   state2 = init;
   nMinusM = n-m;
   while (s <= nMinusM) {
      state1 = init;
      j = s+beta;
      end = s+m;
      while ((j < end) && (getTarget(state1, y[j]) != UNDEFINED)) {
         state1 = getTarget(state1, y[j]);
         ++j;
      }

      if (j < s+m) {
       state2 = getSuffixLink(state1);
         while ((state2 != init) && (getTarget(state2, y[j]) == UNDEFINED)) {
            state2 = getSuffixLink(state2);
         }
         if (getTarget(state2, y[j]) != UNDEFINED) {
            ell = getLength(state2) + 1;
            state2 = getTarget(state2, y[j]);
         }
         else {
            ell = 0;
            state2 = init;
         }
         ++j;
      }
      else {
         j = s+ell;
      }
      end = s+m;
      while (((j < end) || (ell < alpha)) && (j < n)) {
         if (getTarget(state2, y[j]) != UNDEFINED) {
            ++ell;
            state2 = getTarget(state2, y[j]);
         }
         else {
            while ((state2 != init) && (getTarget(state2, y[j]) == UNDEFINED)) {
               state2 = getSuffixLink(state2);
            }
            if (getTarget(state2, y[j]) != UNDEFINED) {
               ell = getLength(state2) + 1;
               state2 = getTarget(state2, y[j]);
            }
            else {
               ell = 0;
               state2 = init;
            }
         }
         if (ell == m) {
            OUTPUT(j-m+1);
            state2 = getSuffixLink(state2);
            ell = getLength(state2);
         }
         ++j;
      }
      s = j-ell;
   }
   free(ttrans);
   free(tlength);
   free(tsuffix);
   return count;
}