Ukkonen的后缀树算法

小开

我的直觉如下：

在主循环的k次迭代之后，您构建了一个后缀树，其中包含以前k个字符开头的完整字符串的所有后缀。

在开始时，这意味着后缀树包含一个代表整个字符串的根节点（这是唯一从0开始的后缀）。

在len（string）迭代之后，您有一个包含所有后缀的后缀树。

在循环过程中，关键是活动点。我的猜测是，这代表了后缀树中对应于字符串前k个字符的正确后缀的最深点。（我认为正确意味着后缀不能是整个字符串。）

例如，假设您已经看到字符'abCabc'。活动点将表示树中与后缀'abc'对应的点。

活动点由（起源，第一，最后）表示。这意味着您目前处于树中的点，您可以从节点原点开始，然后输入字符串[first： last]中的字符

添加新字符时，您会查看活动点是否仍在现有树中。如果是，那么你就完成了。否则，您需要在活动点向后缀树添加一个新节点，回退到下一个最短匹配，然后再次检查。

注1：后缀指针为每个节点提供下一个最短匹配的链接。

注2：当您添加新节点和回退时，您为新节点添加了一个新的后缀指针。此后缀指针的目的地将是缩短的活动点处的节点。这个节点要么已经存在，要么在这个回退循环的下一次迭代中创建。

注3：经典化部分简单地节省了检查活动点的时间。例如，假设您始终使用的是原值=0，并且只更改了第一个和最后一个。要检查活动点，您必须每次沿着所有中间节点跟踪后缀树。通过记录与最后一个节点的距离来缓存遵循此路径的结果是有意义的。

你能给出一个代码示例来说明你所说的“修复”边界变量的含义吗？

健康警告：我也发现这个算法特别难以理解，所以请意识到这种直觉可能在所有重要细节上都不正确。

小开

最佳答案

下面试图描述Ukkonen算法，首先展示它在字符串简单（即不包含任何重复字符）时的作用，然后将其扩展到完整算法。

首先是一些初步陈述。

我们正在构建的是基本上，就像一个搜索Trie。所以有是一个根节点，从它出去的边导致新的节点，并且更多的边离开这些，等等
但是：与搜索Trie不同，边缘标签不是单一的相反，每条边都使用一对整数进行标记[from,to]。这些是指向文本的指针。从这个意义上说，每个Edge携带任意长度的字符串标签，但只需要O（1）空格（两个指针）。

基本原则

我想首先演示如何创建后缀树特别简单的字符串，没有重复字符的字符串：

abc

算法按步骤工作，从左到右。有为字符串的每个字符执行一个步骤。每一步可能涉及多个单独的操作，但是我们会看到（参见最后的观察结果）操作的总数是O（n）。

所以，我们从左开始，首先只插入单个字符a通过创建从根节点（左侧）到叶子的边，并将其标记为[0,#]，这意味着边缘代表子字符串从位置0开始，到当前结束结束。我使用符号#表示当前结束，它位于位置1（a之后）

所以我们有一个初始树，它看起来像这样：

它的意思是：

现在我们前进到位置2（在b之后）。我们每一步的目标是插入到当前位置的所有后缀。我们这样做由

将现有的a边缘扩展到ab
为b插入一条新边

在我们看来

输入图片描述

它的意思是：

我们观察两件事：

ab的边表示是相同，因为它曾经是在初始树中：[0,#]。它的含义已自动更改因为我们将当前位置#从1更新为2。
每个边消耗O（1）个空间，因为它只由两个边组成指向文本的指针，无论它有多少个字符表示。

接下来我们再次增加位置并通过附加c到每个现有边，并为新边插入一个新边后缀c.

在我们看来

它的意思是：

我们观察到：

树是正确的后缀树直到当前位置每一步之后
文本中有多少个字符就有多少个步骤
每一步的工作量为O（1），因为所有现有的边通过递增#自动更新，并插入最终字符的一个新边可以在O（1）时间。因此，对于长度为n的字符串，只需要O（n）时间。

第一个扩展：简单重复

当然，这只是因为我们的字符串没有很好地工作包含任何重复。我们现在看一个更现实的字符串：

abcabxabcd

与前面的示例一样，它以abc开头，然后重复ab然后是x，然后是abc，然后是d。

步骤1到3：在前3步之后，我们得到了上一个示例中的树：

步骤4：我们将#移动到位置4。这会隐式更新所有现有的下一篇：

我们需要插入当前步骤的最后一个后缀，a，在根。

在我们这样做之前，我们引入还有两个变量（除了#），当然一直在那里，但我们没有使用到目前为止：

活动点，这是一个三元组(active_node,active_edge,active_length)
remainder，这是一个整数，表示有多少新后缀我们需要插入

这两个词的确切含义很快就会变得清晰，但现在我只能说：

在简单的abc示例中，活动点始终是(root,'\0x',0)，即active_node是根节点，active_edge被指定为空字符'\0x'，active_length为零。这样做的效果是我们插入的每一步都插入根节点作为新创建的边缘。我们很快就会看到为什么三重是必要的表示此信息。
remainder在每个开始时总是设置为1步骤。这意味着我们必须使用的后缀数量在每个步骤结束时主动插入为1（始终只是最后一个字符）。

现在这将改变。当我们插入当前的最终在根目录中的字符a，我们注意到已经有一个传出边缘从a开始，具体地说：abca。这是我们在这样的例子：

我们不要在根节点插入一个新边[4,#]。相反，我们只需注意到后缀a已经在我们的树。它在一个较长的边缘的中间结束，但我们不是为此而烦恼。我们只是让事情保持原样。
我们设置活动点到(root,'a',1)。这意味着活动point现在位于以a开头的根节点的传出边缘的中间位置，特别是在该边缘的位置1之后。我们请注意，边仅由其第一个指定字符a。这就足够了，因为可以有只有一个边以任何特定字符开头（在阅读整个描述后确认这是真的）。
我们也递增remainder，所以在下一步的开始这将是2。

意见：当我们需要插入的最后一个后缀被找到时已经存在于树中，树本身就是没有改变（我们只更新活动点和remainder）。树然后不是后缀树的准确表示，直到当前位置任何更多，但它包含所有后缀（因为最终后缀a包含隐含）。因此，除了更新变量（都是固定长度的，所以这是O（1）），有在这一步中没有做任何工作。

步骤5：我们将当前位置#更新为5。这自动将树更新为：

和因为#0是2，我们需要插入两个最终当前位置的后缀：ab和b。这基本上是因为：

上一步的a后缀从未正确插入。因此它具有仍然，并且由于我们已经进行了一个步骤，它现在已经从a增长到ab。
我们需要插入新的最终边缘b。

在实践中，这意味着我们去活动点（它指向在a后面，现在是abcab边缘），并插入当前最终字符b。但是：再次，事实证明b是也已经存在于同一边缘。

所以，同样，我们不改变树。我们只是：

将活动点更新为(root,'a',2)（相同的节点和边缘和以前一样，但是现在我们指向后面的b）
将remainder增加到3，因为我们仍然没有正确地插入上一步的最后一条边，我们不插入当前的最终边缘。

需要明确的是：我们必须在当前步骤中插入ab和b，但是因为已经找到了ab，所以我们更新了活动点并做了甚至没有尝试插入b。为什么？因为如果ab在树中，其中每个后缀（包括b）必须在树中，也许只有隐含，但它一定在那里，因为到目前为止，我们已经建立了树。

我们通过递增#前进到步骤6。树是自动更新到：

因为#0是3，我们必须插入abx，bx和x。活动点告诉我们ab在哪里结束，所以我们只需要跳转到那里并插入x。事实上，x还不在那里，所以我们分割abcabx边并插入一个内部节点：

边缘表示仍然是指向文本的指针，因此分割和插入内部节点可以在O（1）时间内完成。

所以我们已经处理了abx和递减remainder到2。现在我们需要插入下一个剩余的后缀bx。但在我们这样做之前我们需要更新活动点。分裂后的规则并插入边缘，将在下面称为规则1，并且它适用于active_node是root（我们将进一步学习规则3）下面是规则1：

从root插入后，

active_node仍然是root
active_edge设置为新后缀we的第一个字符需要插入，即b
active_length减少了1

因此，新的活动点三元组(root,'b',1)表示下一个插入必须在bcabx边缘，在1个字符后面，即在b后面。我们可以在O（1）时间内识别插入点检查x是否已经存在。如果存在，我们将结束当前步骤并保持一切原样。但是x不存在，因此我们通过拆分边缘来插入它：

同样，这花费了O（1）时间，我们将remainder更新为1活动点(root,'x',0)作为规则1状态。

但我们还需要做一件事。我们称之为规则2：

如果我们分割一条边并插入一个新节点，如果这不是在当前步骤中创建的第一个节点，我们连接前面的插入的节点和新节点通过一个特殊的指针，一个后缀我们稍后会看到为什么这是有用的。这是我们得到的后缀链接表示为虚线边：

我们仍然需要插入当前步骤的最终后缀，x.由于活动节点的active_length组件已经下降到0，最后的插入直接在根处进行。由于没有从x开始的根节点的传出边，我们插入一个新的边缘：

正如我们所看到的，在当前步骤中，所有剩余的插入都已完成。

我们通过设置#=7继续步骤7，这会自动追加下一个字符，a，到所有叶边，一如既往。然后我们尝试插入新的最后一个字符到活动点（根），并发现它在那里所以我们结束当前步骤而不插入任何内容将活动点更新为(root,'a',1)。

在步骤8中，#=8，我们追加b，如前所述，这仅意味着我们将活动点更新为(root,'a',2)并递增remainder而不做然而，我们注意到（在O（1）时间内）活动点现在位于边缘的末端。我们通过将其重新设置为(node1,'\0x',0)。在这里，我使用node1来指代ab边结束的内部节点。

然后，在步骤#0=9中，我们需要插入'c'，这将帮助我们了解最后的技巧：

第二个扩展：使用后缀链接

与往常一样，#更新会自动将c附加到叶边缘然后我们去活动点，看看我们是否可以插入'c'。它转out'c'已经存在于该边缘，因此我们将活动点设置为(node1,'c',1)，递增remainder，什么也不做。

现在在步骤#0=10中，remainder是4，所以我们首先需要插入abcd（从3步前保持）通过在活动位置插入d点。

尝试在活动点插入d会导致边缘分裂O（1）时间：

拆分是从active_node开始的，标记为上面的红色。这是最终规则，规则3：

从不是根的active_node中拆分一条边后节点，我们遵循该节点的后缀链接，如果有任何，并将active_node重置为它指向的节点。如果有没有后缀链接，我们将active_node设置为根。active_edgeactive_length保持不变。

所以活动点现在是(node2,'c',1)，node2被标记为红色：

由于abcd的插入完成，我们将remainder递减为3并考虑当前步骤的下一个剩余后缀，bcd。规则3已将活动点设置为正确的节点和边缘所以插入bcd可以通过简单地插入它的最终字符来完成d在活动点。

这样做会导致另一个边缘分裂，并且由于规则2，我们必须创建从先前插入的节点到新节点的后缀链接一：

我们观察到：后缀链接使我们能够重置活动点，以便我们可以在O（1）下进行下一个剩余插入努力。看看上图确认标签ab的节点确实链接到b处的节点（其后缀），abc处的节点链接到bc.

当前步骤尚未完成。remainder现在是2，我们需要遵循规则3再次重置活动点。由于当前active_node（上面红色）没有后缀链接，我们重置为root。活动点现在是(root,'c',1)。

因此，下一个插入发生在根节点的一个传出边缘其标签以c开头：cabxabcd，在第一个字符后面，即c后面。这会导致另一个拆分：

由于这涉及到创建一个新的内部节点，我们遵循规则2并从先前创建的内部设置一个新的后缀链接节点：

（我正在使用GraphvizDot来处理这些小问题图。新的后缀链接导致点重新排列现有的所以要仔细检查以确认唯一上面插入的是一个新的后缀链接。）

有了这个，remainder可以设置为1，因为active_node是root，我们使用规则1将活动点更新为(root,'d',0)。这表示当前步骤的最后插入是插入单个d在根：

这是最后一步，我们完成了。有许多最终评论：

在每一步中，我们将#向前移动1个位置。这会自动在O（1）时间内更新所有叶节点。
但它不处理a）任何前缀剩余步骤，以及b）当前步骤的最后一个字符。
remainder告诉我们需要多少额外的插入使。这些插入与最后的后缀一一对应结束于当前位置#的字符串。我们考虑一个重要提示：每个插入是在O（1）时间内完成，因为活动点告诉我们确切的位置开始，我们只需要在活动中添加一个字符点。为什么？因为其他字符是隐含（否则活动点不会在它所在的位置）。
在每次这样的插入之后，我们递减remainder并遵循如果有后缀链接。如果没有，我们去根（规则3）。如果我们已经在根中，我们使用规则1修改活动点。在在任何情况下，它只需要O（1）时间。
如果在其中一个插入中，我们发现我们想要的字符插入已经存在，我们不做任何事情并结束当前步骤，即使remainder>0。原因是任何剩下的插入将是我们刚刚尝试的那个的后缀因此，它们在当前树中都是隐式。事实remainder>0确保我们处理剩余的后缀稍后。
如果在算法remainder>0的末尾呢？这将是当文本末尾是发生的子字符串时的case之前的某个地方。在这种情况下，我们必须附加一个额外的字符在以前未发生的字符串的末尾。在通常，美元符号$被用作这有什么关系？-->如果稍后我们使用完成的后缀树来搜索后缀，我们必须只接受结束于一片叶子的匹配。否则我们会得到很多虚假的匹配，因为树中包含的许多字符串隐含不是主字符串的实际后缀。强制remainder在末尾为0本质上是一种确保所有后缀都以叶节点结尾的方法。然而，如果我们想使用树来搜索一般子串，而不仅仅是主字符串的后缀，这最后一步确实是不需要的，正如下面OP的评论所建议的那样。
那么整个算法的复杂度是多少？如果文本是n在长度上，显然有n个步骤（如果我们加上n+1）在每一步中，我们要么什么都不做（除了更新变量），或者我们做remainder个插入，每个插入取O（1）时间。因为remainder表示我们有多少次什么都没做在前面的步骤中，并且对于我们进行的每次插入都递减现在，我们做某事的总次数正好是n（或因此，总复杂度是O（n）。
但是，有一件小事我没有正确解释：它可能发生，我们按照后缀链接，更新活动点，然后发现它的active_length组件不与新的active_node配合得很好。例如，考虑一种情况像这样：

（虚线表示树的其余部分。虚线是后缀链接。）

现在让活动点为(red,'d',3)，因此它指向该位置在defg边缘的f后面。现在假设我们做了必要的更新，现在按照后缀链接更新活动点根据规则3。新的活动点是(green,'d',3)。然而，从绿色节点出去的d边是de，所以它只有2为了找到正确的激活点，我们显然需要跟随该边到蓝色节点并重置为(blue,'f',1)。

在特别糟糕的情况下，active_length可能会像remainder，它可以和n一样大。它很可能会发生为了找到正确的激活点，我们不仅需要跳过一个内部节点，但可能很多，最坏情况下最多可达n。这样做意味着算法有一个隐藏的O（n²）复杂度，因为在每个步骤remainder通常为O（n），并且后调整后缀链接后的活动节点也可能是O（n）？

不，原因是如果我们确实必须调整活动点（例如，从绿色到蓝色，如上所述），这将我们带到一个新的节点有自己的后缀链接，active_length将被简化。作为我们顺着后缀链接链进行剩余的插入，active_length只能减少，以及我们可以进行的活动点调整的数量在任何给定时间内，路径都不能大于active_length。因为active_length永远不会大于remainder，并且remainder不仅在每一步中是O（n），而且是增量的总和remainder在整个过程中是O（n），活动点调整的数量也有界O（n）.

小开

我试着用jogo日本给出的方法实现后缀树，但由于规则使用的措辞，它在某些情况下不起作用。此外，我提到过没有人能用这种方法实现绝对正确的后缀树。下面我将写一个jogo日本答案的“概述”，对规则进行一些修改。我还将描述当我们忘记创建重要后缀链接的情况。

使用的附加变量

活动点-三元组（active_node；active_edge；active_length），显示我们必须从哪里开始插入新后缀。
剩余-显示我们必须添加明确的后缀数。例如，如果我们的单词是'abcaabca'，余数=3，这意味着我们必须处理3个最后的后缀：bca、ca和一个。

让我们使用内部节点的概念-所有节点，除了root和利夫斯是内部节点。

意见1

当我们需要插入的最后一个后缀已经存在于树中时，树本身根本没有改变（我们只更新active point和remainder）。

意见2

如果在某个点active_length大于或等于当前边的长度（edge_length），我们将active point向下移动，直到edge_length严格大于active_length。

现在，让我们重新定义规则：

规则1

如果在插入活动节点=root之后，有效长度大于0，则：

活动节点没有改变
有效长度递减
活动边向右移动（到我们必须插入的下一个后缀的第一个字符）

规则2

如果我们创建一个新的内部节点或从内部节点制作一个插入器，并且这不是当前步骤中的第一个这样内部节点，那么我们将之前的这样节点与这个节点链接到后缀链接。

Rule 2的定义不同于jogo日本，因为这里我们不仅考虑了新创建内部节点，还考虑了内部节点，我们从中进行插入。

第3

插入不是root节点的活动节点后，我们必须遵循后缀链接并将活动节点设置为它指向的节点。如果没有后缀链接，请将活动节点设置为root节点。无论哪种方式，活动边和有效长度都保持不变。

在Rule 3的这个定义中，我们还考虑了叶节点的插入（不仅仅是分裂节点）。

最后，观察3：

当我们想要添加到树中的符号已经在边缘时，我们根据Observation 1只更新active point和remainder，保持树不变。但是如果有一个内部节点标记为需要后缀链接，我们必须通过后缀链接将该节点与我们当前的active node连接起来。

让我们看一下cdddcdc的后缀树的例子，如果我们在这种情况下添加后缀链接，如果我们不这样做：

如果我们不要通过后缀链接连接节点：

在添加最后一个字母c之前：

添加最后一个字母c后：

如果我们DO通过后缀链接连接节点：

在添加最后一个字母c之前：

似乎没有显著差异：在第二种情况下，还有两个后缀链接。但是这些后缀链接是，其中一个——从蓝色节点到红色节点——对于我们处理的方法来说非常。问题是，如果我们这里不放后缀链接，稍后，当我们向树中添加一些新字母时，我们可能会由于Rule 3而省略向树中添加一些节点，因为根据它，如果没有后缀链接，那么我们必须将active_node放在根上。

当我们将最后一个字母添加到树中时，在我们从蓝色节点（标记为'c'的边缘）插入之前，红色节点具有已经存在。由于蓝色节点有一个插入，我们将其标记为需要后缀链接。然后，依靠活动点的方法，active node被设置为红色节点。但是我们不从红色节点进行插入，因为字母'c'已经在边缘上了。这是否意味着蓝色节点必须没有后缀链接？不，我们必须通过后缀链接将蓝色节点与红色节点连接起来。为什么是正确的？因为活动点方法保证我们到达正确的位置，即下一个必须处理更短后缀插入的位置。

最后，以下是我对后缀树的实现：

Java
C++

希望这个“概述”与jogoJapan的详细回答相结合，将有助于有人实现他自己的后缀树。

小开

嗨，我已经尝试用ruby实现上述解释的实现，请查看。看起来效果不错

实现的唯一区别是，我尝试使用边缘对象而不仅仅是使用符号。

它也存在于https://gist.github.com/suchitpuri/9304856

require 'pry' class Edgeattr_accessor :data , :edges , :suffix_linkdef initialize data@data = data@edges = []@suffix_link = nilend def find_edge elementself.edges.each do |edge|return edge if edge.data.start_with? elementendreturn nilendend class SuffixTreesattr_accessor :root , :active_point , :remainder , :pending_prefixes , :last_split_edge , :remainder def initialize@root = Edge.new nil@active_point = { active_node: @root , active_edge: nil , active_length: 0}@remainder = 0@pending_prefixes = []@last_split_edge = nil@remainder = 1end def build stringstring.split("").each_with_index do |element , index| add_to_edges @root , element update_pending_prefix elementadd_pending_elements_to_tree elementactive_length = @active_point[:active_length] # if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data[0..active_length-1] == @active_point[:active_edge].data[active_length..@active_point[:active_edge].data.length-1])# @active_point[:active_edge].data = @active_point[:active_edge].data[0..active_length-1]# @active_point[:active_edge].edges << Edge.new(@active_point[:active_edge].data)# end if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data.length == @active_point[:active_length] )@active_point[:active_node] = @active_point[:active_edge]@active_point[:active_edge] = @active_point[:active_node].find_edge(element[0])@active_point[:active_length] = 0endendend def add_pending_elements_to_tree element to_be_deleted = []update_active_length = false# binding.pryif( @active_point[:active_node].find_edge(element[0]) != nil)@active_point[:active_length] = @active_point[:active_length] + 1@active_point[:active_edge] = @active_point[:active_node].find_edge(element[0]) if @active_point[:active_edge] == nil@remainder = @remainder + 1returnend @pending_prefixes.each_with_index do |pending_prefix , index| # binding.pry if @active_point[:active_edge] == nil and @active_point[:active_node].find_edge(element[0]) == nil @active_point[:active_node].edges << Edge.new(element) else @active_point[:active_edge] = node.find_edge(element[0]) if @active_point[:active_edge] == nil data = @active_point[:active_edge].datadata = data.split("") location = @active_point[:active_length] # binding.pryif(data[0..location].join == pending_prefix or @active_point[:active_node].find_edge(element) != nil ) else #tree splitsplit_edge data , index , elementend endendend def update_pending_prefix elementif @active_point[:active_edge] == nil@pending_prefixes = [element]return end @pending_prefixes = [] length = @active_point[:active_edge].data.lengthdata = @active_point[:active_edge].data@remainder.times do |ctr|@pending_prefixes << data[-(ctr+1)..data.length-1]end @pending_prefixes.reverse! end def split_edge data , index , elementlocation = @active_point[:active_length]old_edges = []internal_node = (@active_point[:active_edge].edges != nil) if (internal_node)old_edges = @active_point[:active_edge].edges@active_point[:active_edge].edges = []end @active_point[:active_edge].data = data[0..location-1].join@active_point[:active_edge].edges << Edge.new(data[location..data.size].join) if internal_node@active_point[:active_edge].edges << Edge.new(element)else@active_point[:active_edge].edges << Edge.new(data.last)end if internal_node@active_point[:active_edge].edges[0].edges = old_edgesend #setup the suffix linkif @last_split_edge != nil and @last_split_edge.data.end_with?@active_point[:active_edge].data @last_split_edge.suffix_link = @active_point[:active_edge]end @last_split_edge = @active_point[:active_edge] update_active_point index end def update_active_point indexif(@active_point[:active_node] == @root)@active_point[:active_length] = @active_point[:active_length] - 1@remainder = @remainder - 1@active_point[:active_edge] = @active_point[:active_node].find_edge(@pending_prefixes.first[index+1])elseif @active_point[:active_node].suffix_link != nil@active_point[:active_node] = @active_point[:active_node].suffix_linkelse@active_point[:active_node] = @rootend@active_point[:active_edge] = @active_point[:active_node].find_edge(@active_point[:active_edge].data[0])@remainder = @remainder - 1endend def add_to_edges root , elementreturn if root == nilroot.data = root.data + element if(root.data and root.edges.size == 0)root.edges.each do |edge|add_to_edges edge , elementendendend suffix_tree = SuffixTrees.newsuffix_tree.build("abcabxabcd")binding.pry

小开

@jogoJapan你带来了很棒的解释和可视化。但是正如@makongov提到的，它缺少一些关于设置后缀链接的规则。当通过单词'aabaaabb'在http://brenden.github.io/ukkonen-animation/上一步一步时，它很好地可见。当你从第10步到第11步时，从节点5到节点2没有后缀链接，但是活动点突然移动到那里。

由于我生活在Java世界，我也试图遵循您的实施来掌握ST构建工作流程，但这对我来说很难，因为：

结合边与节点
使用索引指针而不是引用
中断语句；
继续声明；

因此，我最终在Java实现了这样的实现，我希望它以更清晰的方式反映所有步骤，并将减少其他Java人的学习时间：

import java.util.Arrays;import java.util.HashMap;import java.util.Map; public class ST { public class Node {private final int id;private final Map<Character, Edge> edges;private Node slink; public Node(final int id) {this.id = id;this.edges = new HashMap<>();} public void setSlink(final Node slink) {this.slink = slink;} public Map<Character, Edge> getEdges() {return this.edges;} public Node getSlink() {return this.slink;} public String toString(final String word) {return new StringBuilder().append("{").append("\"id\"").append(":").append(this.id).append(",").append("\"slink\"").append(":").append(this.slink != null ? this.slink.id : null).append(",").append("\"edges\"").append(":").append(edgesToString(word)).append("}").toString();} private StringBuilder edgesToString(final String word) {final StringBuilder edgesStringBuilder = new StringBuilder();edgesStringBuilder.append("{");for(final Map.Entry<Character, Edge> entry : this.edges.entrySet()) {edgesStringBuilder.append("\"").append(entry.getKey()).append("\"").append(":").append(entry.getValue().toString(word)).append(",");}if(!this.edges.isEmpty()) {edgesStringBuilder.deleteCharAt(edgesStringBuilder.length() - 1);}edgesStringBuilder.append("}");return edgesStringBuilder;} public boolean contains(final String word, final String suffix) {return !suffix.isEmpty()&& this.edges.containsKey(suffix.charAt(0))&& this.edges.get(suffix.charAt(0)).contains(word, suffix);}} public class Edge {private final int from;private final int to;private final Node next; public Edge(final int from, final int to, final Node next) {this.from = from;this.to = to;this.next = next;} public int getFrom() {return this.from;} public int getTo() {return this.to;} public Node getNext() {return this.next;} public int getLength() {return this.to - this.from;} public String toString(final String word) {return new StringBuilder().append("{").append("\"content\"").append(":").append("\"").append(word.substring(this.from, this.to)).append("\"").append(",").append("\"next\"").append(":").append(this.next != null ? this.next.toString(word) : null).append("}").toString();} public boolean contains(final String word, final String suffix) {if(this.next == null) {return word.substring(this.from, this.to).equals(suffix);}return suffix.startsWith(word.substring(this.from,this.to)) && this.next.contains(word, suffix.substring(this.to - this.from));}} public class ActivePoint {private final Node activeNode;private final Character activeEdgeFirstCharacter;private final int activeLength; public ActivePoint(final Node activeNode,final Character activeEdgeFirstCharacter,final int activeLength) {this.activeNode = activeNode;this.activeEdgeFirstCharacter = activeEdgeFirstCharacter;this.activeLength = activeLength;} private Edge getActiveEdge() {return this.activeNode.getEdges().get(this.activeEdgeFirstCharacter);} public boolean pointsToActiveNode() {return this.activeLength == 0;} public boolean activeNodeIs(final Node node) {return this.activeNode == node;} public boolean activeNodeHasEdgeStartingWith(final char character) {return this.activeNode.getEdges().containsKey(character);} public boolean activeNodeHasSlink() {return this.activeNode.getSlink() != null;} public boolean pointsToOnActiveEdge(final String word, final char character) {return word.charAt(this.getActiveEdge().getFrom() + this.activeLength) == character;} public boolean pointsToTheEndOfActiveEdge() {return this.getActiveEdge().getLength() == this.activeLength;} public boolean pointsAfterTheEndOfActiveEdge() {return this.getActiveEdge().getLength() < this.activeLength;} public ActivePoint moveToEdgeStartingWithAndByOne(final char character) {return new ActivePoint(this.activeNode, character, 1);} public ActivePoint moveToNextNodeOfActiveEdge() {return new ActivePoint(this.getActiveEdge().getNext(), null, 0);} public ActivePoint moveToSlink() {return new ActivePoint(this.activeNode.getSlink(),this.activeEdgeFirstCharacter,this.activeLength);} public ActivePoint moveTo(final Node node) {return new ActivePoint(node, this.activeEdgeFirstCharacter, this.activeLength);} public ActivePoint moveByOneCharacter() {return new ActivePoint(this.activeNode,this.activeEdgeFirstCharacter,this.activeLength + 1);} public ActivePoint moveToEdgeStartingWithAndByActiveLengthMinusOne(final Node node,final char character) {return new ActivePoint(node, character, this.activeLength - 1);} public ActivePoint moveToNextNodeOfActiveEdge(final String word, final int index) {return new ActivePoint(this.getActiveEdge().getNext(),word.charAt(index - this.activeLength + this.getActiveEdge().getLength()),this.activeLength - this.getActiveEdge().getLength());} public void addEdgeToActiveNode(final char character, final Edge edge) {this.activeNode.getEdges().put(character, edge);} public void splitActiveEdge(final String word,final Node nodeToAdd,final int index,final char character) {final Edge activeEdgeToSplit = this.getActiveEdge();final Edge splittedEdge = new Edge(activeEdgeToSplit.getFrom(),activeEdgeToSplit.getFrom() + this.activeLength,nodeToAdd);nodeToAdd.getEdges().put(word.charAt(activeEdgeToSplit.getFrom() + this.activeLength),new Edge(activeEdgeToSplit.getFrom() + this.activeLength,activeEdgeToSplit.getTo(),activeEdgeToSplit.getNext()));nodeToAdd.getEdges().put(character, new Edge(index, word.length(), null));this.activeNode.getEdges().put(this.activeEdgeFirstCharacter, splittedEdge);} public Node setSlinkTo(final Node previouslyAddedNodeOrAddedEdgeNode,final Node node) {if(previouslyAddedNodeOrAddedEdgeNode != null) {previouslyAddedNodeOrAddedEdgeNode.setSlink(node);}return node;} public Node setSlinkToActiveNode(final Node previouslyAddedNodeOrAddedEdgeNode) {return setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, this.activeNode);}} private static int idGenerator; private final String word;private final Node root;private ActivePoint activePoint;private int remainder; public ST(final String word) {this.word = word;this.root = new Node(idGenerator++);this.activePoint = new ActivePoint(this.root, null, 0);this.remainder = 0;build();} private void build() {for(int i = 0; i < this.word.length(); i++) {add(i, this.word.charAt(i));}} private void add(final int index, final char character) {this.remainder++;boolean characterFoundInTheTree = false;Node previouslyAddedNodeOrAddedEdgeNode = null;while(!characterFoundInTheTree && this.remainder > 0) {if(this.activePoint.pointsToActiveNode()) {if(this.activePoint.activeNodeHasEdgeStartingWith(character)) {activeNodeHasEdgeStartingWithCharacter(character, previouslyAddedNodeOrAddedEdgeNode);characterFoundInTheTree = true;}else {if(this.activePoint.activeNodeIs(this.root)) {rootNodeHasNotEdgeStartingWithCharacter(index, character);}else {previouslyAddedNodeOrAddedEdgeNode = internalNodeHasNotEdgeStartingWithCharacter(index,character, previouslyAddedNodeOrAddedEdgeNode);}}}else {if(this.activePoint.pointsToOnActiveEdge(this.word, character)) {activeEdgeHasCharacter();characterFoundInTheTree = true;}else {if(this.activePoint.activeNodeIs(this.root)) {previouslyAddedNodeOrAddedEdgeNode = edgeFromRootNodeHasNotCharacter(index,character,previouslyAddedNodeOrAddedEdgeNode);}else {previouslyAddedNodeOrAddedEdgeNode = edgeFromInternalNodeHasNotCharacter(index,character,previouslyAddedNodeOrAddedEdgeNode);}}}}} private void activeNodeHasEdgeStartingWithCharacter(final char character,final Node previouslyAddedNodeOrAddedEdgeNode) {this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);this.activePoint = this.activePoint.moveToEdgeStartingWithAndByOne(character);if(this.activePoint.pointsToTheEndOfActiveEdge()) {this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();}} private void rootNodeHasNotEdgeStartingWithCharacter(final int index, final char character) {this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));this.activePoint = this.activePoint.moveTo(this.root);this.remainder--;assert this.remainder == 0;} private Node internalNodeHasNotEdgeStartingWithCharacter(final int index,final char character,Node previouslyAddedNodeOrAddedEdgeNode) {this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);if(this.activePoint.activeNodeHasSlink()) {this.activePoint = this.activePoint.moveToSlink();}else {this.activePoint = this.activePoint.moveTo(this.root);}this.remainder--;return previouslyAddedNodeOrAddedEdgeNode;} private void activeEdgeHasCharacter() {this.activePoint = this.activePoint.moveByOneCharacter();if(this.activePoint.pointsToTheEndOfActiveEdge()) {this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();}} private Node edgeFromRootNodeHasNotCharacter(final int index,final char character,Node previouslyAddedNodeOrAddedEdgeNode) {final Node newNode = new Node(idGenerator++);this.activePoint.splitActiveEdge(this.word, newNode, index, character);previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);this.activePoint = this.activePoint.moveToEdgeStartingWithAndByActiveLengthMinusOne(this.root,this.word.charAt(index - this.remainder + 2));this.activePoint = walkDown(index);this.remainder--;return previouslyAddedNodeOrAddedEdgeNode;} private Node edgeFromInternalNodeHasNotCharacter(final int index,final char character,Node previouslyAddedNodeOrAddedEdgeNode) {final Node newNode = new Node(idGenerator++);this.activePoint.splitActiveEdge(this.word, newNode, index, character);previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);if(this.activePoint.activeNodeHasSlink()) {this.activePoint = this.activePoint.moveToSlink();}else {this.activePoint = this.activePoint.moveTo(this.root);}this.activePoint = walkDown(index);this.remainder--;return previouslyAddedNodeOrAddedEdgeNode;} private ActivePoint walkDown(final int index) {while(!this.activePoint.pointsToActiveNode()&& (this.activePoint.pointsToTheEndOfActiveEdge() || this.activePoint.pointsAfterTheEndOfActiveEdge())) {if(this.activePoint.pointsAfterTheEndOfActiveEdge()) {this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(this.word, index);}else {this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();}}return this.activePoint;} public String toString(final String word) {return this.root.toString(word);} public boolean contains(final String suffix) {return this.root.contains(this.word, suffix);} public static void main(final String[] args) {final String[] words = {"abcabcabc$","abc$","abcabxabcd$","abcabxabda$","abcabxad$","aabaaabb$","aababcabcd$","ababcabcd$","abccba$","mississipi$","abacabadabacabae$","abcabcd$","00132220$"};Arrays.stream(words).forEach(word -> {System.out.println("Building suffix tree for word: " + word);final ST suffixTree = new ST(word);System.out.println("Suffix tree: " + suffixTree.toString(word));for(int i = 0; i < word.length() - 1; i++) {assert suffixTree.contains(word.substring(i)) : word.substring(i);}});}}

小开

感谢@陈志立解释得很好的教程，我用Python实现了算法。

@jogoJapan提到的几个小问题结果比我预期的要多复杂，需要非常小心地对待。我花了几天时间才实现足够强大（我想）。问题和解决方案如下：

事实证明，这种情况也可能发生在展开步骤中，而不仅仅是整个算法的结束。当这种情况发生时，我们可以保持余数actnode、actedge和actl的不变，结束当前的展开步骤，并开始另一个步骤，根据原始字符串中的下一个字符是否在当前路径上保持折叠或展开。
跳过节点：当我们跟随后缀链接时，更新活动点，然后发现其active_length组件不能与新active_node很好地配合使用。我们必须将向前迈进移到正确的位置来拆分或插入叶子。这个过程可能是没那么简单，因为在移动过程中actl的长度和actedge一直在变化，当您必须移回根节点时，actedge和长度可能是错误，因为这些移动。我们需要额外的变量来保存该信息。

另外两个问题已经被@陈志立指出了

当尝试分割边缘时，有时你会发现分割操作正好在一个节点上。这种情况下，我们只需要在该节点上添加一个新的叶子，将其作为标准的边缘分割操作，这意味着如果有后缀链接，应该相应地维护。
还有一种特殊情况，就是问题1和问题2会引起后缀链接。有时我们需要跳过多个节点到正确的点进行拆分，如果我们通过比较余数字符串和路径标签来移动，我们可能会超过正确的点。这种情况后缀链接将在无意中被忽略，如果应该有的话。这可以通过在前进时记住正确的点来避免。如果拆分节点已经存在，甚至问题1发生在展开步骤中，则应保留后缀链接。

最后，我在python中的实现如下：

Python

温馨提示：它在上面的代码中包含了一个简单的树打印函数，这在调试时非常重要。它节省了我很多时间和方便查找特殊情况。

小开

如果我的回答似乎是多余的，我很抱歉，但我最近实施了Ukkonen的算法，发现自己在这方面挣扎了好几天；我不得不通读关于这个主题的多篇论文，以了解算法的一些核心方面的原因和方式。

我发现之前答案中的“规则”方法无助于理解潜在的0，所以我把所有内容写在下面，只关注语用学。如果你像我一样难以理解其他解释，也许我的补充解释会让你“点击”。

我在这里发布了我的C#实现：https://github.com/baratgabor/SuffixTree

请注意，我不是这方面的专家，因此以下部分可能包含不准确之处（或更糟）。如果您遇到任何问题，请随时编辑。

先决条件

以下解释的起点假设您熟悉后缀树的内容和使用，以及Ukkonen算法的特征，例如如何从头到尾逐个字符扩展后缀树。基本上，我假设您已经阅读了其他一些解释。

（然而，我确实必须为流程添加一些基本的叙述，所以开头可能确实觉得多余。

最有趣的部分是解释使用后缀链接和从根重新扫描的区别。这给我的实现带来了很多错误和头痛。

开放式叶节点及其局限性

我相信你已经知道最基本的“技巧”是意识到我们可以让后缀的结尾“打开”，即引用字符串的当前长度而不是将结尾设置为静态值。这样，当我们添加其他字符时，这些字符将隐式添加到所有后缀标签中，而无需访问和更新所有字符。

但是这种后缀的开放结尾——出于显而易见的原因——仅适用于表示字符串结尾的节点，即树结构中的叶节点。我们在树上执行的分支操作（添加新的分支节点和叶节点）不会自动传播到它们需要的任何地方。

重复的子字符串不会显式地出现在树中，这可能是基本的，不需要提及，因为树已经包含了这些子字符串，因为它们是重复的；然而，当重复的子字符串遇到一个不重复的字符时，我们需要在该点创建一个分支来表示从该点开始的发散。

例如，在字符串ABCXABCY（见下文）的情况下，需要将X和Y的分支添加到三个不同的后缀，abc，BC和C；否则它将不是有效的后缀树，并且我们无法通过从根向下匹配字符来找到字符串的所有子字符串。

再次强调，我们对树中的后缀执行的-任何操作也需要由其连续后缀反映（例如ABC>BC>C），否则它们就不再是有效的后缀。

但是，即使我们接受必须进行这些手动更新，我们如何知道有多少后缀需要更新？因为，当我们添加重复字符一个（以及接下来的重复字符）时，我们还不知道何时/何处需要将后缀拆分为两个分支。只有当我们遇到第一个不重复字符时才确定需要拆分，在这种情况下是Y（而不是树中已经存在的X）。

我们可以做的是匹配我们可以重复的最长字符串，并计算我们以后需要更新的后缀数量。这就是“剩余”代表的。

“剩余”和“撤销”的概念

变量remainder告诉我们在没有分支的情况下隐式添加了多少重复字符；也就是说，一旦我们找到第一个无法匹配的字符，我们需要访问多少后缀来重复分支操作。这基本上等于我们在树中从根开始有多少个字符“深”。

所以，保持前面的字符串ABCXABCY的例子，我们“隐式”匹配重复的abc部分，每次递增remainder，这导致3的余数。然后我们遇到了不重复的字符是。在这里，我们将之前添加的ABCX拆分为abc->X和abc->remainder1。然后我们将remainder从3减少到2，因为我们已经处理了abc的分支。现在我们重复操作，匹配最后2个字符-remainder3-从根到需要拆分的地方，我们将remainder4也拆分为remainder3->X和remainder3->remainder1。同样，我们将remainder递减为1，并重复操作；直到remainder为0。最后，我们还需要将当前字符（remainder1）本身添加到根。

这个操作，从根开始跟踪连续的后缀，只是为了到达我们需要进行操作的点，在Ukkonen的算法中被称为“撤销”，通常这是算法中最昂贵的部分。想象一个更长的字符串，你需要跨几十个节点“重新扫描”长的子字符串（我们稍后会讨论），可能需要数千次。

作为解决方案，我们引入了所谓的后缀链接。

“后缀链接”的概念

后缀链接基本上指向我们通常必须重新扫描的位置，因此我们可以简单地跳转到链接位置，执行我们的工作，跳转到下一个链接位置，然后重复-直到没有更多的位置要更新。

当然，一个大问题是如何添加这些链接。现有的答案是，我们可以在插入新分支节点时添加链接，利用这样一个事实，在树的每个扩展中，分支节点是按照我们需要将它们链接在一起的确切顺序自然创建的。但是，我们必须从最后一个创建的分支节点（最长后缀）链接到之前创建的分支节点，因此我们需要缓存上次创建的分支节点，链接到下一个创建的分支节点，并缓存新创建的分支节点。

一个后果是我们实际上通常没有后缀链接要遵循，因为给定的分支节点刚刚创建。在这种情况下，我们仍然必须从root回退到前面提到的“撤销”。这就是为什么在插入后，你被指示要么使用后缀链接，要么跳转到root。

（或者，如果您在节点中存储父指针，您可以尝试跟踪父指针，检查它们是否有链接，并使用它。我发现这很少被提及，但是后缀链接用法不设置在石头中。有多种可能的方法，如果您了解底层机制，您可以实现最适合您需求的方法。）

“活动点”的概念

到目前为止，我们讨论了构建树的多种有效工具，并模糊地提到了遍历多个边和节点，但还没有探索相应的后果和复杂性。

前面解释的“剩余”概念对于跟踪我们在树中的位置很有用，但我们必须意识到它没有存储足够的信息。

首先，我们总是驻留在节点的特定边缘上，因此我们需要存储边缘信息。我们将此称为主动边缘。

其次，即使添加了边缘信息，我们仍然无法识别树中更远的位置，并且不直接连接到root节点。所以我们还需要存储节点。让我们称之为主动节点。

最后，我们可以注意到“剩余”不足以识别不直接连接到根的边缘上的位置，因为“剩余”是整个路由的长度；我们可能不想费心记住和减去前面的边的长度。所以我们需要一个本质上是当前边缘上的余数的表示。这就是我们所说的活动长度。

这导致了我们所谓的活动点——一个包含三个变量的包，其中包含我们需要维护的关于我们在树中的位置的所有信息：

Active Point = (Active Node, Active Edge, Active Length)

您可以在下图中观察ABCABD的匹配路径是如何由AB边缘的2个字符（来自root）加上CABDABCABD边缘的4个字符（来自节点4）组成的-导致“剩余”的6个字符。所以，我们当前的位置可以被识别为活动节点4、活动边缘C、活动长度4。

活动点的另一个重要作用是它为我们的算法提供了一个抽象层，这意味着我们的部分算法可以在活动点上执行它们的工作，而不管该活动点是在根中还是在其他任何地方。这使得在我们的算法中以干净和直接的方式实现后缀链接的使用变得容易。

重新扫描与使用后缀链接的差异

现在，棘手的部分，根据我的经验，可能会导致大量的错误和头痛，并且在大多数来源中解释得很差，是处理后缀链接情况与重新扫描情况的差异。

考虑字符串'AAAABAAABAAC'的以下示例：

您可以在上面观察到，7中的“剩余”对应于根节点的字符总和，而4中的活动长度对应于活动节点活动边缘的匹配字符总和。

现在，在活动点执行分支操作后，我们的活动节点可能包含也可能不包含后缀链接。

如果存在后缀链接：我们只需要处理活动长度部分。“剩余”是无关紧要的，因为我们通过后缀链接跳转到的节点已经隐式编码了正确的“余数”，仅仅是因为它在树中。

如果后缀链接不存在：我们需要从零/根开始重新扫描，这意味着从一开始就处理整个后缀。为此，我们必须使用整个“剩余”作为重新扫描的基础。

使用和不使用后缀链接的处理示例比较

考虑一下上面示例的下一步会发生什么。让我们比较一下如何在有和没有后缀链接的情况下实现相同的结果——即移动到下一个要处理的后缀。

使用'后缀链接'

请注意，如果我们使用后缀链接，我们会自动“在正确的位置”。由于活动长度可能与新位置“不兼容”，这通常不是严格正确的。

在上面的例子中，由于活动长度是4，我们从链接的节点4开始使用后缀'ABAA'。但是在找到与后缀（'A'）的第一个字符对应的边缘后，我们注意到我们的活动长度将此边缘溢出了3个字符。因此我们跳过完整边缘到下一个节点，并将活动长度减去我们在跳转中消耗的字符。

然后，在我们找到下一个边'B'之后，对应于递减后缀'BAA'，我们最终注意到边长度大于3中的剩余活动长度，这意味着我们找到了正确的位置。

请注意，似乎这个操作通常不被称为“重新扫描”，即使对我来说，它似乎是重新扫描的直接等价物，只是缩短了长度和非根起点。

使用'重新扫描'

请注意，如果我们使用传统的“重新扫描”操作（这里假装我们没有后缀链接），我们从树的顶部开始，从根开始，我们必须再次向下到正确的位置，沿着当前后缀的整个长度。

这个后缀的长度是我们之前讨论过的“剩余”。我们必须消耗整个余数，直到它达到零。这可能（而且经常）包括跳过多个节点，在每次跳过时将余数减少我们跳过的边缘的长度。然后最后，我们到达一条比剩余的“剩余”长的边缘；这里我们将活动边缘设置为给定边缘，将活动长度设置为剩余的'剩余'，我们就完成了。

然而，请注意，实际的“剩余”变量需要保留，并且仅在每次节点插入后递减。所以我上面描述的假设使用初始化为“剩余”的单独变量。

关于后缀链接和回复的注释

1）请注意，这两种方法都会导致相同的结果。然而，后缀链接跳转在大多数情况下要快得多；这就是后缀链接背后的全部原理。

2）实际的算法实现不需要不同。正如我上面提到的，即使在使用后缀链接的情况下，活动长度通常与链接的位置不兼容，因为树的该分支可能包含额外的分支。所以本质上你只需要使用活动长度而不是“剩余”，并执行相同的重新扫描逻辑，直到找到比剩余后缀长度更短的边。

3）关于性能有一点很重要，那就是在重新扫描时没有必要检查每个字符。由于构建有效后缀树的方式，我们可以安全地假设字符匹配。所以你主要是在计算长度，当我们跳到一个新边缘时，唯一需要字符等价检查的是，因为边缘是由它们的第一个字符识别的（在给定节点的上下文中总是唯一的）。这意味着“重新扫描”逻辑不同于完整字符串匹配逻辑（即在树中搜索子字符串）。

4）这里描述的原始后缀链接只是可能的方法之一。例如NJ Larsson等人。将这种方法命名为面向节点的自上而下，并将其与面向节点的自下而上方法和两个面向边缘品种进行比较。不同的方法有不同的典型和最坏情况性能、需求、局限性等，但通常看起来面向边缘方法是对原始方法的整体改进。