后缀树是一种数据结构,它支持有效的字符串匹配和查询。 一个具有m个词的字符串S的后缀树T,就是一个包含一个根节点的有向树,该树恰好带有m个叶子,这些叶子被赋予从1到m的标号。 每一个内部节点,除了根节点以外,都至少有两个子节点,而且每条边都用S的一个非空子串来标识。出自同一节点的任意两条边的标识不会以相同的词开始。后缀 树的关键特征是:对于任何叶子i,从根节点到该叶子所经历的边的所有标识串联起来后恰好拼出S的从i位置开始的后缀,即Si,...,m。树中节点的标识 被定义为从根到该节点的所有边的标识的串联。