后缀树可以看做是建立在trie之上的数据结构，在该结构中，您不仅可以将字符串本身添加到trie中，还可以添加该字符串的所有可能的后缀。例如，如果要在后缀树中索引banana 字符串，则可以使用以下字符串构建特里：

banana
anana
nana
ana
na
a

完成后，您可以搜索任何n-gram并查看它是否存在于索引字符串中。换句话说，n-gram搜索是字符串所有可能后缀的前缀搜索。

这是构建后缀树的最简单，最慢的方法。事实证明，此数据结构上有许多更高级的变体，它们既可以改善空间又可以改善构建时间。我对这一领域并不精通，没有一个概述，但是您可以从研究后缀数组或此类高级数据结构开始（第16和18节）。