Content deleted Content added
Nils Grimsmo (talk | contribs) No edit summary |
Nils Grimsmo (talk | contribs) mNo edit summary |
||
Line 1:
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 <math>S</math> of length <math>n</math>, or a set of documents <math>D=\{S^1,S^2, \dots, S^d\}</math> of total length <math>n</math>, you can locate all occurences of a pattern <math>P</math> in <math>o(n)</math> time. (<math>o(n)</math> means less than <math>O(n)</math>. See [[Big O notation]].)
The phrase '''full-text index''' is also often used for an index of all substrings of a text. But is ambiguous, as it is also used for regular word indexes such as [[inverted file]]s and [[signature file]]s. See [[full text search]].
Substring indexes include:
| |||