Substring index: Difference between revisions

Revision as of 20:03, 12 December 2024

Latest revision as of 08:19, 10 January 2025

(One intermediate revision by one other user not shown)

Line 26:

| title = Combinatorial Pattern Matching, 9th Annual Symposium, CPM 98, Piscataway, New Jersey, USA, July 20–22, 1998, Proceedings

| volume = 1448

| year = 1998}}</ref>| isbn = 978-3-540-64739-3

}}</ref>

==Examples==

Line 45 ⟶ 46:

| title = Automata, Languages and Programming, 11th Colloquium, Antwerp, Belgium, July 16–20, 1984, Proceedings

| volume = 172

| year = 1984}}</ref>| isbn = 978-3-540-13345-2

}}</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

Line 68 ⟶ 70:

| url = https://www.di.unipi.it/~grossi/PAPERS/sicomp05.pdf

| volume = 35

| year = 2005}}<| hdl = 1808/ref>18962

}}</ref>

* The [[FM-index]], another compressed substring index based on the [[Burrows–Wheeler transform]] and closely related to the suffix array<ref>{{citation

| last1 = Ferragina | first1 = Paolo

Line 84 ⟶ 87:

{{reflist}}

{{Strings|state=collapsed}}

[[Category:Algorithms on strings]]

[[Category:String data structures]]