Suffix automaton: Difference between revisions

Revision as of 09:58, 8 November 2020

Revision as of 00:46, 9 November 2020

Line 9:

}}

In [[computer science]], thea '''suffix automaton''' is an efficient [[data structure]] for representing [[substring index]] of a given string which allows to store, process and retrieve compressed information about all its [[substring]]s. The suffix automaton of a string <math>S</math> ismay thebe represented as a [[directed acyclic graph]] with a dedicated initial vertex and a set of "final" vertices, such that:

# Its [[Arc (graph theory)|arcs]] are tagged with [[Character (computing)|letters]];

Line 15:

# for every suffix of <math>S</math> there exists a path from initial vertex to some final vertex such that the [[concatenation]] of letters on the path forms this suffix;

# it has the least number of vertices among all graphs defined by the properties above.

Speaking in the terms of [[automata theory]], a suffix automaton is the [[Minimal automaton|minimal]] partial [[deterministic finite automaton]] that recognizes the set of [[Substring|suffixes]] of a given [[String (computer science)|string]] <math>S=s_1 s_2 \dots s_n</math>. The [[state graph]] of a suffix automaton is called a directed acyclic word graph (DAWG), a term that is also sometimes used for any [[deterministic acyclic finite state automaton]].