Content deleted Content added
I removed the phrase "o(n) means less than O(n)" as it isn't accurate. |
→top: more references |
||
Line 1:
{{more references}}
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]].)
| |||