# Substring index

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, \dots, S^d\}$ of total length $n$, you can locate all occurrences of a pattern $P$ in $o(n)$ time. (See Big O notation.)