后缀树算法分析与设计 _结点

一、后缀树的定义：通过一个树可以表示所有可能的后缀子串；
例子：S=；
1）每一条边用一个字符串标记；2）所有的后缀可以从根结点到所有叶结点的路径读出；
3）结束标记符“$”（避免某些后缀是其他后缀的前驱）；
后缀树的特点：1）长度为n的字符串，其后缀树恰好有n个叶子结点（因为有n个后缀）；
2）每一条边可以用个数据表示（在原来字符串的起始位置和结束位置）；
【后缀树算法分析与设计】3）在一个后缀树中至多有2n-1个结点；
证明：首先已知有n个叶子结点其度数为0 ，除了根结点和叶子结点每一个内部结点的度数为2 ，根结点度数不定设为x ， x的取值范围为【2 ， n0】在这里设叶子结点为n0 ，度数为2的结点为n2,总结点个数为n易得：n=n0+n2+1;//这里的1为根结点由度数的关系可得出：2*n2+x+1=n;//叶结点不提供分支，根结点提供x个分支，其余结点提供2个分支联立上述两式子可得出：n=2n0+1-x;即可得出节点总数n的取值范围为【n0+1,2n0-1】
4）一个后缀树可以用O（nlogn）位表示；
二、后缀树的简单应用
1）在S中找出所有的出现Q的子串个数：从根结点出发，沿着唯一的路径Q到达点x ，所有x以下的叶子结点均为出现过Q的子串
时间复杂度为O（|Q|+出现次数）总体上呈现线性级；
2）找出S中的最长重复子串：找出具有最大深度的内结点，其所对应的路径即为最长重复子串
时间复杂度为O（n）
3）求解不同序列的最长公共子序列：将不同序列S全部构建在一个后缀树中，每个叶子结点用不同的结点加以标记，找出
具有最大深度的内部结点且此结点同时包含不同串的后缀；
除此之外还有其他应用：如最长匹配、最大回文、最长公共前驱等等；（算法的时间复杂度为O(n)）
三、后缀树构造算法（复杂度O(n^2)）：
1）首先初始化一个树只有一个根结点；O(1)
2）之后循环遍历n次，将各个后缀子串加入到这棵树中；O(n^2)
四、隐含后缀树（方法）：1）将所有的边中的$全部删除；2）去除所有没有标记的边；3）删除只有一个孩子的结点；
（如图所示：隐含后缀树中没有结束标记符，且每个内部结点的孩子个数大于等于2 ，边值用于保存路径信息）
隐含后缀树
Rule1：如果在树中发现与当前匹配S【j ， i】的路径且终止于一个叶子结点，即将S【i+1】加入这条边的末尾即可；
Rule2：如果在树中发现与当前匹配S【j ， i】的路径但其后面的元素不是S【i+1】建立一个新的叶子结点，以及一个
新的内部结点，新旧结点的边标记为S【i+1】，这个新的叶结点标记为i；
Rule3：如果从根节点开始的标记为S【j ， i】的路径终止于非叶节点边（即在该路径上S[i]字符后还有其他字符）而且
下一个字符是S【i+1】（树中已经存在），那么什么也不做。
隐含后缀树的构造，以S=acca为例子（）：
Step1：i=1时，根据规则1可知直接创建一个叶子结点1将边标记为a即可；
Step2：i=2时，对于S=ac ，根据规则1将c加入1叶子结点的上部；对于S=c ，根据规则2创建一个叶子结点2将边标记为c即可；
Step3：i=3时，对于S=acc ，根据规则1将c加入1叶子结点的上部；对于S=cc ，根据规则1将c加入2叶子结点的上部；

后缀树 算法分析与设计

后缀树算法分析与设计