Substring index: Difference between revisions

Revision as of 12:16, 6 December 2021

Revision as of 13:51, 7 June 2022

Line 1:

{{Short description|Data structure}}

{{more references|date=December 2021}}

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 <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 occurrences of a pattern <math>P</math> in <math>o(n)</math> time. (See [[Big O notation]].)