Content deleted Content added
Line 29:
Specific data structures that can be used as substring indexes include:
* The [[suffix tree]], a [[radix tree]] of the suffixes of the string, allowing substring search to be performed symbol-by-symbol<ref name=bst/><ref name=gv/>
* The [[suffix automaton]], a [[deterministic finite automaton]] that recognizes substrings of a given text, closely related to the suffix tree and constructable by variants of the same algorithms.<ref>{{citation
| last1 = Blumer | first1 = Anselm
| last2 = Blumer | first2 = J.
| last3 = Ehrenfeucht | first3 = Andrzej | author3-link = Andrzej Ehrenfeucht
| last4 = Haussler | first4 = David | author4-link = David Haussler
| last5 = McConnell | first5 = Ross M.
| editor-last = Paredaens | editor-first = Jan
| contribution = Building the minimal DFA for the set of all subwords of a word on-line in linear time
| doi = 10.1007/3-540-13345-3_9
| pages = 109–118
| publisher = Springer
| series = Lecture Notes in Computer Science
| title = Automata, Languages and Programming, 11th Colloquium, Antwerp, Belgium, July 16–20, 1984, Proceedings
| volume = 172
| year = 1984}}</ref>
* The [[suffix array]], a sorted array of the starting positions of suffixes of the string, allowing substring search to be performed by [[binary search]]<ref name=bst/><ref name=gv/> Augmenting a suffix array with an [[LCP array]] of the lengths of common prefixes of consecutive suffixes allows the search to be performed symbol-by-symbol, matching the search time of the suffix tree.<ref>{{citation
| last1 = Manber | first1 = Udi | author1-link = Udi Manber
| |||