Substring_index
Substring index
Data structure
In computer science, a substring index is a data structure which gives substring search in a text or text collection in sublinear time. If you have a document of length , or a set of documents of total length , you can locate all occurrences of a pattern in time. (See Big O notation.)
This article needs additional citations for verification. (December 2021) |
The phrase full-text index is also often used for an index of all substrings of a text. But this is ambiguous, as it is also used for regular word indexes such as inverted files and document retrieval. See full text search.
Substring indexes include:
- Suffix tree
- Suffix array
- N-gram index, an inverted file for all N-grams of the text
- Compressed suffix array[1]
- FM-index
- LZ-index