Suffix automaton: Difference between revisions

Revision as of 00:52, 9 November 2020

Revision as of 00:57, 9 November 2020

Line 9:

}}

In [[computer science]], a '''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> is representeda by asmallest [[directed acyclic graph]] with a dedicated initial vertex and a set of "final" vertices, such that paths from the initial vertex to final vertices represent the suffixes of the string. Formally saying, suffix automaton is defined by the following set of properties:

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