Content deleted Content added
Adamant.pwn (talk | contribs) rewriting the lead |
Adamant.pwn (talk | contribs) one more article |
||
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 for a string <math>S</math> of 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.
| |||