Content deleted Content added
Adamant.pwn (talk | contribs) citations |
Adamant.pwn (talk | contribs) citation |
||
Line 314:
The same should be true for the suffix tree because its vertices correspond to states of the suffix automaton of the reversed string but this problem may be resolved by not explicitly storing every vertex corresponding to the suffix of the whole string, thus only storing vertices with at least two out-going edges. A variation of McCreight's suffix tree construction algorithm for this task was suggested in 1989 by Edward Fiala and Daniel Greene;<ref>{{harvp|Fiala, Greene|1989|p=490}}</ref> several years later a similar result was obtained with the variation of [[Ukkonen's algorithm]] by Jesper Larsson.<ref>{{harvp|Larsson|1996}}</ref><ref>{{harvp|Brodnik, Jekovec|2018|p=1}}</ref> The existence of such an algorithm, for compacted suffix automaton that absorbs some properties of both suffix trees and suffix automata, was an open question for a long time until it was discovered by Martin Senft and Tomasz Dvorak in 2008, that it is impossible if the alphabet's size is at least two.<ref>{{harvp|Senft, Dvořák|2008|p=109}}</ref>
One way to overcome this obstacle is to allow window width to vary a bit while staying <math>O(k)</math>. It may be achieved by an approximate algorithm suggested by Inenaga et al. in 2004. The window for which suffix automaton is built in this algorithm is not guaranteed to be of length <math>k</math> but it is guaranteed to be at least <math>k</math> and at most <math>2k+1</math> while providing linear overall complexity of the algorithm.<ref>{{harvp|Inenaga et al.|2004}}</ref>
== Applications ==
Suffix automaton of the string <math>S</math> may be used to solve such problems as:<ref name=":
* Counting the number of distinct substrings of <math>S</math> in <math>O(|S|)</math> on-line,
Line 325:
* Finding all occurrences of <math>T</math> in <math>S</math> in <math>O(|T|+k)</math>, where <math>k</math> is the number of occurrences.
It is assumed here that <math>T</math> is given on the input after suffix automaton of <math>S</math> is constructed.
Suffix automata are also used in data compression,<ref>{{harvp|Yamamoto et al.|2014|loc=|p=675}}</ref> music retrieval<ref>{{harvp|Crochemore et al.|2003|loc=|p=211}}</ref><ref>{{harvp|Mohri et al.|2009|loc=|страницы=|p=3553}}</ref> and matching on genome sequences.<ref>{{harvp|Faro|2016|loc=|p=145}}</ref>
| |||