## Example

\(
\def\sa#1{\tt{#1}}
\def\dd{\dot{}\dot{}}
\def\aArbre{\mathcal{T}}
\def\aSTree{\mathcal{ST}}
\def\aSuff{\mathcal{S}}
\def\aFact{\mathcal{F}}
\def\Suff{\mathit{Suff}}
\)

Below are the trie $\aArbre(\Suff(\sa{aabab}))$ of suffixes of $\sa{aabab}$
(on the left) and its Suffix tree $\aSTree(\sa{aabab})$ (on the right).
To get a complete linear-size structure,
each factor of the word that labels an arc needs to be represented by a pair
of integers such as (position, length).

Below (left) is $\aSuff(\sa{aabab})$, the Suffix automaton of
$\sa{aabab}$.
The right part shows the Factor automaton of
$\sa{aabab}$ in which state 6 of $\aSuff(\sa{aabab})$ is merged
with state 3.

#
Suffix Structures

Suffix structures that store the suffixes of a word are important data
structures used to produce efficient indexes.
Tries can be used as such but their size can be quadratic.
One solution to cope with that is to compact the trie, resulting in the
*Suffix tree* of the word.
It consists in eliminating non-terminal nodes with only one outgoing edge
and in labelling arcs by factors of the word accordingly.
Eliminated nodes are sometimes called implicit nodes of the Suffix tree
and remaining nodes are called explicit nodes.

A second solution to reduce the size of the Suffix trie is to minimise it,
which means considering the minimal deterministic automaton accepting the
suffixes of the word, its *Suffix automaton*.

It is known that $\aSuff(x)$ possesses fewer than $2|x|$ states and fewer
than $3|x|$ arcs, for a total size $O(|x|)$, that is, linear in $|x|$.
The Factor automaton $\aFact(x)$ of the word, minimal deterministic automaton
accepting its factors, can even be smaller because all its states are
terminal.