Suffix automaton: Difference between revisions

Revision as of 00:59, 9 November 2020

Revision as of 12:30, 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 tothe storestorage, processprocessing, and retrieveretrieval of compressed information about all its [[substring]]s. The suffix automaton of a string <math>S</math> is the smallest [[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]];