————《高级数据结构》
1。后缀树的简介
后缀树在1973年被首次提出，当时叫做position tree，该算法能够在线性时间内构建后缀树.，几年之后，又有了另外一种不同的线性算法，这种新算法更加节省空间，可以说是对原来算法的大幅度优化。1995年，在此基础上提出了第一个能在线构建的后缀树，并且该算法以一种更加容易理解的方式呈现。在此之后对后缀树研究，主要是将其应用到不同场景后的变化，如对字符串的适应能力，在外部构建（即借助磁盘构建大型后缀树），压缩以及简化等。
本文主要考虑字符串所包含的字符集固定并且内存足以支撑整个构建的情况。

2、后缀树的定义
假定给定一个长度为m的字符串S（下标从1到m），S的后缀树T为一个有m个叶节点的有根树，其叶节点从1到m编号；除了根节点之外，内个内部节点至少有两个孩子；每条边上都标有S的一个非空子集；从同一个节点引出的任意两条边上标的字符串都不会以相同的字符开始；最后，也是最重要的一点，对任意一个叶节点i，从根节点到i的路径上所有边上标的字符串连接起来，就是S从位置i开始的后缀，也就是说，上述路径恰好拼出了S[i…m],
Trie树，上述后缀树相当于将S的m个后缀看做m个单词插入到字典树中，同时收缩那些只有一个孩子的内部节点。
不过，不是所有的字符串都存在这样的后缀树。例如，如果把上述字符串的最后一个字符c去掉，后缀xa就消失了，因为后缀xa恰好是xabxa的前缀，所以按照上述方式构建出来的树就没有m个叶节点了。因此，其根本问题就是有些后缀会是其他后缀的前缀。为了避免这个问题，我们统一在字符串后添加一个S中没有出现过的字符，不妨用 表 示 。 这 样 ， 字 符 串 S 表示。这样，字符串S 表示。这样，字符串S就一定有对应的后缀树了。
为了方便表示，我们再定义如下几个概念。
路径标记：从根节点到某个节点的路径标记，就是该路径上标记的字符串顺次连接得到的字符串，这称作该节点的路径标记。
字符深度：一个节点的字符深度定义为其路径标记所包含的字符个数。
深度：一个节点的深度定义为其到根节点路径上经过的边数目。

后缀树的构建
在这一节中，我们首先介绍一种易懂但是效率较低的朴素算法，unkonen算法，其原始思想以及直接的暴力实现，然后一步步优化得到最终的线性时间的算法。

3.1 后缀树的朴素构建算法
后缀树可以看做压缩过后的Trie树，所以一种直观的朴素算法就是将字符串S 的 m 个 后 缀 看 做 m 个 单 词 插 入 T r i e 树 中 ， 然 后 按 照 后 缀 树 的 压 缩 规 则 — — 每 个 内 部 节 点 至 少 有 两 个 孩 子 ， 来 对 T r i e 树 中 的 内 部 节 点 压 缩 。 由 于 每 次 插 入 的 时 间 复 杂 度 与 插 入 的 串 长 度 成 正 比 ， 所 以 构 建 T r i e 树 的 时 间 复 杂 度 易 知 为 O （ m 2 ） ， 再 加 上 之 后 的 压 缩 操 作 ， 总 的 时 间 复 杂 度 仍 为 O （ m 的 2 次 方 ） 。 3.2 后 缀 树 的 线 性 时 间 构 造 算 法 在 介 绍 线 性 时 间 构 建 算 法 之 前 ， 我 们 有 必 要 证 明 我 们 的 存 储 结 构 （ 包 含 节 点 个 数 以 及 边 上 标 记 ） 也 至 多 是 线 性 的 。 本 书 介 绍 的 线 性 时 间 构 建 算 法 为 1995 年 由 U k k o n e n 提 出 的 。 该 算 法 想 比 较 其 他 线 性 时 间 算 法 而 言 ， 主 要 有 能 再 构 建 ， 较 容 易 理 解 和 实 现 ， 更 节 省 空 间 等 优 势 。 所 以 为 了 便 于 理 解 ， 我 们 首 先 一 种 朴 素 方 式 低 效 的 实 现 u n k k o n e e n 算 法 ， 然 后 再 进 行 优 化 。 1. 隐 式 树 的 朴 素 构 造 ， u k k o n e n 的 算 法 过 程 主 要 是 构 建 一 系 列 的 “ 隐 式 树 ” ， 其 中 最 后 构 建 的 一 颗 隐 式 树 可 以 将 其 转 变 为 我 们 所 要 的 后 缀 树 。 将 S 的m个后缀看做m个单词插入Trie树中，然后按照后缀树的压缩规则——每个内部节点至少有两个孩子，来对Trie树中的内部节点压缩。由于每次插入的时间复杂度与插入的串长度成正比，所以构建Trie树的时间复杂度易知为O（m^2），再加上之后的压缩操作，总的时间复杂度仍为O（m的2次方）。 3.2后缀树的线性时间构造算法 在介绍线性时间构建算法之前，我们有必要证明我们的存储结构（包含节点个数以及边上标记）也至多是线性的。 本书介绍的线性时间构建算法为1995年由Ukkonen提出的。该算法想比较其他线性时间算法而言，主要有能再构建，较容易理解和实现，更节省空间等优势。所以为了便于理解，我们首先一种朴素方式低效的实现unkkoneen算法，然后再进行优化。 1.隐式树的朴素构造，ukkonen的算法过程主要是构建一系列的“隐式树”，其中最后构建的一颗隐式树可以将其转变为我们所要的后缀树。 将S 的m个后缀看做m个单词插入Trie树中，然后按照后缀树的压缩规则——每个内部节点至少有两个孩子，来对Trie树中的内部节点压缩。由于每次插入的时间复杂度与插入的串长度成正比，所以构建Trie树的时间复杂度易知为O（m2），再加上之后的压缩操作，总的时间复杂度仍为O（m的2次方）。3.2后缀树的线性时间构造算法在介绍线性时间构建算法之前，我们有必要证明我们的存储结构（包含节点个数以及边上标记）也至多是线性的。本书介绍的线性时间构建算法为1995年由Ukkonen提出的。该算法想比较其他线性时间算法而言，主要有能再构建，较容易理解和实现，更节省空间等优势。所以为了便于理解，我们首先一种朴素方式低效的实现unkkoneen算法，然后再进行优化。1.隐式树的朴素构造，ukkonen的算法过程主要是构建一系列的“隐式树”，其中最后构建的一颗隐式树可以将其转变为我们所要的后缀树。将S的后缀树中所有边的标记 删 去 ， 然 后 删 去 那 些 没 有 标 记 的 边 ， 得 到 的 就 是 字 符 串 S 的 隐 式 树 。 同 时 ， 孩 子 数 目 小 于 2 的 内 部 节 点 也 要 被 删 除 。 类 似 的 ， S 的 前 缀 S [ 1... i ] 的 隐 式 树 为 字 符 串 S [ 1.. i ] 删去，然后删去那些没有标记的边，得到的就是字符串S的隐式树。同时，孩子数目小于2的内部节点也要被删除。类似的，S的前缀S[1...i]的隐式树为字符串S[1..i] 删去，然后删去那些没有标记的边，得到的就是字符串S的隐式树。同时，孩子数目小于2的内部节点也要被删除。类似的，S的前缀S[1...i]的隐式树为字符串S[1..i]的后缀树进行上述操作后得到的树。我们用记号Ti代表S的前缀S[1…i]的隐式树，其中i的取值范围为1到m。
我们发现，如果一个字符串的某一个后缀是另一个后缀的前缀，那么该字符串的隐式树的叶节点数量就会少其后缀树，这也正是后缀树构建时加上字符$的用意所在。
unkknen的算法对于每个S的前缀S[1…i]都会构建对应的隐式树Ti，从Ti开始构建，直到Tm构建完成，然后由该隐式树Tm构建我们所需要的后缀树。我们先来看一种该思想的朴素实现方法————一种时间复杂度为O（m的3次方）的算法。
ukkonen的算法可以分为m个阶段，在第i+1个阶段构造对应的隐式树Ti+1，我们通过隐式树Ti来构建Ti+1。由于后缀树的朴素算法可知，第i+1个阶段构建的前置S[1…i+1]的隐式树需要插入s[1…i+1]的i+1个后缀，所以对于第i+1个阶段，我们进一步将其划分为i+1次扩展。在第i+1个阶段的第j次扩展中，我们将S[1…i+1]的后缀S[j…i+1]插入到隐式树中，由于我们是从Ti构建Ti+1，所以我们当前带插入的后缀S[j…i+1]的前缀S[j…i]已经在树中了，我们只需要根据隐式树定义，看有没有需要将字符S[i+1]插入进去。也就是说，第i+1个阶段将字符S[i+1添加进树Ti来构建Ti+1，而第一阶段只需要将字符S[1]添加进T1即可。整个过程的伪代码如下：
（先跑步去辽，回来再看）
伪代码
function buildimplicitTree()
Build TreeT1
for i<-1 to m-1 do
for j<-1 to i+1 do
在当前树中找到字符串S[j…i]对应的位置，然后看是否需要添加字符S[i+1]
End For
End For
下面，我们来证明该朴素实现算法的时间复杂度是O（m^3)。首先，外部的两重循环需要的运行时间为O（m的3次方），每次循环执行的任务都需要查找字符串对应的位置，而在树中找到该串所需要的实践与串长度呈线性关系，因此每次查找所需时间复杂度为O（m），故总时间复杂度为O(m的3次方)。似乎比我们最初提到的简单的暴力实现还要慢！不过不用着急，接下来我们就会看到如何利用我们发现的一些规律和技巧来将其优化。

3.2扩展规则约定
在开始优化之前，我们对每次扩展规则做个约定：在第i+1阶段的第j次扩展将找到S[j…i]的位置，然后保证S[j…i+1]在树中。
规则1：串s[j…i]终止于叶节点，也就是说从根节点到该叶节点的路径标记为串S[j…i]，此时我们只需要将该叶节点的父边的标记最后加上字符s[i+1]即可。
规则2：串S[j…i]对应的位置不是叶节点（可能是中间节点，也可能是某条边的内部位置，因为一条边可以代表某个子串），同时，串Sj…i+1]又不在当前树中，那么我们需要将该树进行扩展————如果S[j…i]对应的位置在边内部，那么需要将该边在该位置拆开，然后添加新的节点，这样保证了S[j…i]终止于一个节点；然后新建一个该节点的子节点（新的叶子节点，其间的边标记为S[i+1]。
规则3：串s[j…i+1]已经在树中找到，那么我们不需要作出任何的修改
上述规则1和规则3比较直观。由图可知，当插入串“bc”时，路径“b’本来在边的内部，所以创建了一个新的节点，然后加入了新的叶子节点，叶子边对应标记"c"。