Forward Dawg Matching algorithm

The Forward Dawg Matching algorithm computes the longest factor of the pattern ending at each position in the text. This is make possible by the use of the smallest suffix automaton (also called DAWG for Directed Acyclic Word Graph) of the pattern. The smallest suffix automaton of a word w is a Deterministic Finite Automaton S(w) = (Q, q₀, T, E). The language accepted by S(w) is L(S(w))={u in ^* :  exists v in ^* such that w=vu}.

The preprocessing phase of the Forward Dawg Matching algorithm consists in computing the smallest suffix automaton for the pattern x. It is linear in time and space in the length of the pattern.

During the searching phase the Forward Dawg Matching algorithm parses the characters of the text from left to right with the automaton S(x) starting with state q₀. For each state q in S(x) the longest path from q₀ to p is denoted by length(q). This structure extensively uses the notion of suffix links. For each state p the suffix link of p is denoted by S[p]. For a state p, let Path(p)=(p₀,p₁, ... ,p) be the suffix path of p such that p₀=p, for 1  i  , p_i=S[p_i-1] and p=q₀. For each text character y[j] sequentially, let p be the current state, then the Forward Dawg Matching algorithm takes a transition defined for y[j] for the first state of Path(p) for which such a transition is defined. The current state p is updated with the target state of this transition or with the initial state q₀ if no transition exists labelled with y[j] from a state of Path(p).

An occurrence of x is found when length(p)=m.

The Forward Dawg Matching algorithm performs exactly n text character inspections.

int FDM(char *x, int m, char *y, int n) {
   int j, init, ell, state;
   Graph aut;
 
   /* Preprocessing */
   aut = newSuffixAutomaton(2*(m + 2), 2*(m + 2)*ASIZE);
   buildSuffixAutomaton(x, m, aut);
   init = getInitial(aut);
 
   /* Searching */
   ell = 0;
   state = init;
   for (j = 0; j < n; ++j) {
      if (getTarget(aut, state, y[j]) != UNDEFINED) {
         ++ell;
         state = getTarget(aut, state, y[j]);
      }
      else {
         while (state != init &&
                getTarget(aut, state, y[j]) == UNDEFINED)
            state = getSuffixLink(aut, state);
         if (getTarget(aut, state, y[j]) != UNDEFINED) {
            ell = getLength(aut, state) + 1;
            state = getTarget(aut, state, y[j]);
         }
         else {
            ell = 0;
            state = init;
         }
      }
      if (ell == m)
         OUTPUT(j - m + 1);
   }
}