code

Improved Linear DAWG Matching

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


int search(unsigned char *x, int m, unsigned char *y, int n) {
   int k,i,j, R, L, r, ell, end, count, l;
   int *ttrans, *tlength, *tsuffix;
   int *ttransSMA;
   unsigned char *tterminal;
   unsigned char *xR;

   xR = (char*) malloc (sizeof(char)*(m+1));
   for (i=0; i<m; i++) xR[i] = x[m-i-1];
   xR[m] = '\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(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);

   /* Searching */
   count = 0;
   k = m-1;
   while ( k < n ) {
      L = 0 ; R = 0; l = 0;
      while ( k-l >= 0 && ( L = getTarget(L, y[k-l]) ) != UNDEFINED ) {
         l++;
         if ( isTerminal(L) ) R = l ;
      }
      while ( R > 0 ) {
         if ( R==m ) OUTPUT(k-m+1);
         k++ ;
         if ( k >= n ) break;
         R = getSMA(R, y[k]) ;
      }
      k = k + m ;
   }

   free(ttransSMA);
   free(ttrans);
   free(tlength);
   free(tsuffix);
   free(tterminal);
   return count;
}