Suffix automaton: Difference between revisions

Revision as of 00:45, 26 October 2020

Revision as of 00:51, 26 October 2020

Line 16:

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

Suffix automata were introduced in 1983 by a group of scientists from the [[University of Denver]] and the [[University of Colorado Boulder]]. They suggested a [[linear time]] [[online algorithm]] for its construction and showed that forthe suffix automaton of a string <math>S</math> ofhaving length at least two characters, a suffix automaton has at most <math display="inline">2|S| - 1</math> states and at most <math display="inline">3|S| - 4 </math> transitions. Further works have shown a close connection between suffix automata and [[suffix tree]]s, and have outlined several generalizations of suffix automata, such as compacted suffix automaton obtained by compression of nodes with a single outgoing arc.

Suffix automata provide efficient solutions to problems such as [[substring search]] and computation of the [[Longest common substring problem|largest common substring]] of two and more strings.