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.