Revision as of 20:01, 12 December 2024 edit David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,633 edits suffix automaton ← Previous edit		Revision as of 20:01, 12 December 2024 edit undo David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,633 edits minimal Next edit →
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]], athe minimal [[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.

Substring index: Difference between revisions