如何以及何时在后缀树中创建后缀链接？
任何人都可以给我一个关于如何以及何时在后缀树中创建后缀链接的例子吗？
如果我的字符串是ABABABC ，但如果更好，请使用其他示例。
希望能够给出一些图片来说明每一步。
非常感谢。
为了理解这一点，首先回顾一下后缀树中有三种节点：
在下图（ ABABABC的后缀树）中，黄色圆圈是根 ，灰色，蓝色和绿色是内部节点 ，小黑色是叶子。
有两件重要的事情需要注意：
内部节点始终有多于1个传出边缘 。 也就是说，内部节点标记出现分支的树的那些部分。
只要有重复的字符串出现，就会出现分支。 对于任何内部节点X，从根到X的字符串在输入字符串中的出现次数必须至少与从X 输出的边相同 。
示例：通向蓝色节点的字符串是ABAB 。 事实上，这个字符串在输入字符串中出现两次：位置0和位置2.这就是蓝色节点存在的原因。
现在关于后缀链接：
如果字符串s领导到一些内部节点X长于1个字符， 相同的字符串减去第一个字符 （称之为S-1）必须在树上，太（这是一个后缀树，毕竟，这样的后缀它的任何字符串也必须在树中）。
示例：设s = ABAB ，即通向蓝色节点的字符串。 然后删除第一个字符后，s-1是BAB 。 事实上，该字符串也可以在树中找到。 它通向绿色节点。
如果某些字符串s通向内部节点，则其缩短的版本s-1 必须导致内部节点（称为X-1）。 为什么？ 由于S1必须在输入字符串中出现至少两次，所以S-1必须至少出现多次（因为它是S的一部分：哪里出来，用 S-1必须出现，太）。 但是如果s-1在输入字符串中出现多次，那么它必须有一个内部节点。
在任何这种情况下，连接X到X-1的特殊链接都是后缀链接。
注意：由于上面的（1）和（2）， 每个从根到X大于1个字符的标签的内部节点X 必须有一个后缀链接到另一个内部节点。
例：
这是和以前一样的后缀树; 虚线表示后缀链接。 如果您从蓝色节点开始，然后从后面跟随后缀链接（从蓝色到绿色，再到第一个灰色，再到第二个灰色），然后查看从根节点到每个节点的字符串，您将看到以下内容：
ABAB -> BAB -> AB -> B
(blue) (green) (gray1) (gray2)
这就是为什么他们被称为后缀链接 （整个序列称为后缀链 ）。
他们有什么好处？
他们对于许多事情出乎意料的好。 然而，他们在Ukkonen的后缀树构造算法中发挥了特殊作用，特别是在这里描述的规则3中：在某个点X处插入了一些后缀s的最后一个字符后，该算法需要插入后缀s-1的最后一个字符在O（1）时间。 为了做到这一点，它使用后缀链接向右跳到地点X-1并进行插入。
但是，请注意 ，没有必要在后缀树中添加后缀链接。 它们不是后缀树定义的一部分 - 它们只是构建或使用后缀树的一些算法所使用的特殊链接。
关于单字符节点：如果有一个内部节点X，它的字符串（即从根到X的路径上的字符串）只包含一个字符会怎样？ 根据上面的定义，X然后没有后缀链接。 但是，你可以假设它有一个后缀链接，它会指向根节点。 此外，如果根据上面的定义，内部节点没有后缀链接，则它必须是单字节节点，因此您始终可以假设，如果内部节点上没有后缀链接，则它必须是单字节节点，字符节点，因此表示s-1后缀的节点是根节点。 （在这种情况下，某些算法实际上可能会添加指向根节点的显式后缀链接。）感谢j_random_hacker提供有关此的评论。
链接地址: http://www.djcxy.com/p/40079.html