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  of length , or a set of documents  of total length , you can locate all occurrences of a pattern  in  time. (See Big O notation.) The phrase full-text index is also often used for an index of all substrings of a text. But this is ambiguous, as it is also used for regular word indexes such as inverted files and document retrieval. See full text search. Substring indexes include:

 Suffix tree
 Suffix array
 N-gram index, an inverted file for all N-grams of the text
 Compressed suffix array
 FM-index
 LZ-index

References 

Algorithms on strings
String data structures
Database index techniques