- uses the suffix automaton of
*x*; (**O***n*) worst case time complexity;- performs exactly
*n*text character inspections.

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*(

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*(

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

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

The function ` buildSuffixAutomaton` is given chapter Reverse Factor algorithm. All the other functions to build and manipulate the suffix automaton can be found in the introduction, section

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); } }

Preprocessing phase

Suffix automaton used by Forward Dawg Matching Search algorithm.

Searching phase

- CROCHEMORE, M., RYTTER, W., 1994, Text Algorithms,
*Oxford University Press*.

Tue Jan 14 15:03:31 MET 1997