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

...
Wikipedia