code

Wide Window

The Wide Window algorithm
ww.c
#include "include/AUTOMATON.h"

void preSMARev(unsigned char *x, int m, int *ttransSMA) {
   int c, i, state, target, oldTarget;

   memset(ttransSMA, 0, SIGMA*sizeof(int));
   for (state = 0, i = m-1; i >= 0; --i) {
      oldTarget = getSMA(state, x[i]);
      target = state+1;
      setSMA(state, x[i], target);
      for (c = 0; c < SIGMA; ++c)
         setSMA(target, c, getSMA(oldTarget, c));
      state = target;
   }
}

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;
   unsigned char *tterminal;
   unsigned char *xR;
 
   /* 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);

   /* Searching */
   count = 0;
   ttransSMA = (int *)malloc((m+1)*SIGMA*sizeof(int));
   memset(ttransSMA, -1, (m+1)*SIGMA*sizeof(int));
   preSMARev(x, m, ttransSMA);
   end = n/m;
   if (n%m > 0) ++end;
   for (k = 1; k < end; ++k) {
      R = L = r = ell = 0;
      while (R != UNDEFINED && k*m-1+r < n) {
         R = getTarget(R, y[k*m-1+r]);
         ++r;
         if (R != UNDEFINED && isTerminal(R))
            L = r;
      }
      while (L > ell) {
         if (L == m) OUTPUT(k*m-1-ell);
         ++ell;
         if (ell == m)
            break;
         L = getSMA(L, y[k*m-1-ell]);
      }
   }
   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(tterminal);
   free(ttransSMA);
   return count;
}