A Generalized Suffix Tree, based on the Ukkonen's paper "On-line construction of suffix trees" http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf
Allows for fast storage and fast(er) retrieval by creating a tree-based index out of a set of strings. Unlike common suffix trees, which are generally used to build an index out of one (very) long string, a Generalized Suffix Tree can be used to build an index over many strings.
Its main operations are put and search:
-
putadds the given key to the index, allowing for later retrieval of the given value. -
searchcan be used to retrieve the set of all the values that were put in the index with keys that contain a given input.
In particular, after put(K, V), search(H) will return a set containing V for any string H that is substring of K.
The overall complexity of the retrieval operation (search) is O(m) where m is the length of the string to search within the index.
Read full article from jefferyyuan/suffixtree-1
