主要思想是:如果S包含S1,那么S1必定是S的某个后缀的前缀;又因为S的后缀树包含了所有的后缀,所以只需对S的后缀树使用和Trie相同的查找方法查找S1即可(使用后缀树实现的复杂度同流行的KMP算法的复杂度相当...和普通树不同的地方是,相同的字符串前缀共享同一条分支。下面,再举一个例子。...本文接下来的所有描述和代码都是基于Esko Ukkonen的成果.
对于所给的文本T, Esko Ukkonen的算法是由一棵空树开始, 逐步构造T的每个前缀的后缀树....那么要构造下一个前缀BOOKK的后缀树的话, 只需要访问树中已存在的每一个后缀, 然后在它们的末尾加上K.
前4个后缀BOOK, OOK, OK和K都在叶节点上结束....这意味着, 每一个前缀更新完之后, 当前的结束节点将成为下一轮更新的激活节点.
好了, 现在我们可以把后缀树的更新限制在激活节点和结束节点之间, 效率有了很大的改善.