Suffix automaton

In computer science, a suffix automaton or directed acyclic word graph is a finite automaton that recognizes the set of suffixes of a given string. It can be thought of as a compressed form of the suffix tree, a data structure that efficiently represents the suffixes of the string. For example, a suffix automaton for the string "suffix" can be queried for other strings; it will report "true" for any of the strings "suffix", "uffix", "ffix", "fix", "ix" and "x", and "false" for any other string.

The suffix automaton of a set of strings U has at most 2Q − 2 states, where Q is the number of nodes of a prefix-tree representing the strings in U.

Suffix automata have applications in approximate string matching.