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

对于S=c ，根据规则3不做任何处理；
Step4：i=4时，对于S=acca ，根据规则1将a加入1叶子结点的上部；对于S=cca ，根据规则1将a加入2叶子结点的上部；
对于S=ca ，根据规则2将健一个新的叶子结点3和一个内部结点（边值为a）；对于S=c ，根据规则3不做任何处理；
（下图为T3变换为T4的后缀树构建，也就是STEP4所解释的）
说的简单一点就是每一次添加新的后缀前先判断这个后缀在树中是否存在如果不存在则直接创建，如果存在根据其后面的
元素来进行对应的操作1）到达叶子时：直接插入到叶边；2）未到达叶子：创建一个新的叶子结点边标记为S【i+1】与内
部结点相连；
构建算法：（1、初始化一棵树；2、循环遍历n-1次将树从Ti变换到Ti+1 ，对于内层循环逐渐更新后缀树通过β=S【j ， i】路径
来根据三种规则将S【i+1】添加至树中）
内外层循环时间复杂度为O(n^2) ，对于每一次的扩展找β的位置时间复杂度为O(|β|) ，所以总体的时间复杂度为O(n^3)；
观察1：规则3一旦使用，其后面的操作均可以省略（减少执行次数，是一个停止规则）
证明：当我们用Rule3扩展β=S【j ， i】时，在树中一定存在一个路径以S【i+1】结束路径；所以对于其后面的路径
也一定有以S【i+1】结束路径；（使用Rule3 break即可）
换一种说法就是β=S【j ， i】的后缀一定在这颗树中所以一旦在S【j ， i】中Rule3那么其其它的后缀也一定满足此条件；
观察2：叶子一旦被创建就不会改变（不会被删除或修改）；（一日为叶子终身为叶子）
技巧：对于任意一颗隐含后缀树，其内部结点除了根结点都有一个后缀链；
对于一个内部结点v其路径标签为xα ，如果存在其他结点s(v)其路径标签为α ，称v指向s(v)的链为后缀链( link)

后缀树 算法分析与设计( 二 )

后缀树算法分析与设计( 二 )