code

Reverse Factor

The Reverse Factor algorithm
rf.c
#include "include/AUTOMATON.h"

void buildSuffixAutomaton(unsigned char *x, int m, int *ttrans, int *tlength, int *tsuffix, unsigned char *tterminal) {
   int i, art, init, last, p, q, r, counter;
   unsigned char c;

   init = 0;
   art = 1;
   counter = 2;
   setSuffixLink(init, art);
   last = init;
   for (i = m-1; i >= 0; --i) {
      c = x[i];
      p = last;
      q = newState();
      setLength(q, getLength(p) + 1);
      while (p != init &&
             getTarget(p, c) == UNDEFINED) {
         setTarget(p, c, q);
         p = getSuffixLink(p);
      }
      if (getTarget(p, c) == UNDEFINED) {
         setTarget(init, c, q);
         setSuffixLink(q, init);
      }
      else
         if (getLength(p) + 1 == getLength(getTarget(p, c)))
            setSuffixLink(q, getTarget(p, c));
         else {
            r = newState();
            //copyVertex(r, getTarget(p, c));
            memcpy(ttrans+r*SIGMA, ttrans+getTarget(p, c)*SIGMA, SIGMA*sizeof(int));
            setSuffixLink(r, getSuffixLink(getTarget(p, c)));
            setLength(r, getLength(p) + 1);
            setSuffixLink(getTarget(p, c), r);
            setSuffixLink(q, r);
            while (p != art && getLength(getTarget(p, c)) >= getLength(r)) {
               setTarget(p, c, r);
               p = getSuffixLink(p);
            }
         }
      last = q;
   }
   setTerminal(last);
   while (last != init) {
      last = getSuffixLink(last);
      setTerminal(last);
   }
}

int search(unsigned char *x, int m, unsigned char *y, int n) {
   int i, j, shift, period, init, state, count;
   int *ttrans, *tlength, *tsuffix;
   unsigned char *tterminal;
   int mMinus1, nMinusm, size;
 
   /* Preprocessing */
   mMinus1 = m-1;
   nMinusm = n-m;
   size = 2*m+3;
   ttrans = (int *)malloc(size*SIGMA*sizeof(int));
   tlength = (int *)calloc(size, sizeof(int));
   tsuffix = (int *)calloc(size, sizeof(int));
   tterminal = (unsigned char *)calloc(size, sizeof(unsigned char));
   memset(ttrans, -1, (2*m+3)*SIGMA*sizeof(int));
   buildSuffixAutomaton(x, m, ttrans, tlength, tsuffix, tterminal);
   init = 0;
   period = m;
 
   /* Searching */
   count = 0;
   if (strncmp(x, y, m) == 0)
      OUTPUT(0);
   j = 1;
   while (j <= nMinusm) {
      i = mMinus1;
      state = init;
      shift = m;
      while (getTarget(state, y[i + j]) != UNDEFINED) {
         state = getTarget(state, y[i + j]);
         if (isTerminal(state)) {
            period = shift;
            shift = i;
         }
         --i;
      }
      if (i < 0) {
         OUTPUT(j);
         shift = period;
      }
      j += shift;
   }
   free(ttrans);
   free(tlength);
   free(tsuffix);
   free(tterminal);
   return count;
}