Substring index explained

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

S of length n , or a set of documents D = \{S ^{1,S} ^{2,} ... , S ^{d\}} of total length n , you can locate all occurrences of a pattern P in o(n) time. (See Big O notation.)

The phrase full-text index is also often used for an index of all substrings of a text.^[1] 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^[2]
• FM-index
• LZ-index

Notes and References

1. Pei, J. . Wu, W. C.-H. . Yeh, M.-Y. . 2013 . On shortest unique substring queries . 2013 IEEE 29th International Conference on Data Engineering (ICDE) . Brisbane, QLD, Australia . IEEE . 937–948 . 10.1109/ICDE.2013.6544887.
2. R. Grossi and J. S. Vitter, Compressed Suffix Arrays and Suffix Trees, with Applications to Text Indexing and String Matching, SIAM Journal on Computing, 35(2), 2005, 378–407.