我的直觉如下:

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

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

在len(string)迭代之后，您将得到一个包含所有后缀的后缀树。

在循环过程中，关键是活动点。我的猜测是，这表示后缀树中最深的点，对应于字符串的前k个字符的适当后缀。(我认为合适的意思是后缀不能是整个字符串。)

例如，假设你见过字符'abcabc'。活动点将表示树中对应后缀'abc'的点。

活动点由(原点，第一个，最后一个)表示。 这意味着你目前在树中的点上，你可以从节点原点开始，然后输入字符串[first:last]中的字符。

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

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

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

注意3:封圣部分只是节省了检查活动点的时间。 例如，假设您总是使用origin=0，只是改变了第一个和最后一个。 为了检查活动点，您必须每次沿着所有中间节点跟随后缀树。 通过只记录到最后一个节点的距离来缓存遵循这条路径的结果是有意义的。

您能给出一个代码示例来说明“修复”边界变量是什么意思吗?

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

感谢@jogojapan精心解释的教程，我在Python中实现了算法。

@jogojapan提到的几个小问题比我想象的要复杂，需要非常谨慎地对待。我花了好几天时间来使我的实现足够健壮(我想)。问题及解决方法如下:

End with Remainder > 0 It turns out this situation can also happen during the unfolding step, not just the end of the entire algorithm. When that happens, we can leave the remainder, actnode, actedge, and actlength unchanged, end the current unfolding step, and start another step by either keep folding or unfolding depending on if the next char in the original string is on the current path or not. Leap Over Nodes: When we follow a suffix link, update the active point, and then find that its active_length component does not work well with the new active_node. We have to move forward to the right place to split, or insert a leaf. This process might be not that straightforward because during the moving the actlength and actedge keep changing all the way, when you have to move back to the root node, the actedge and actlength could be wrong because of those moves. We need additional variable(s) to keep that information.

@managonov以某种方式指出了另外两个问题

Split Could Degenerate When trying to split an edge, sometime you'll find the split operation is right on a node. That case we only need add a new leaf to that node, take it as a standard edge split operation, which means the suffix links if there's any, should be maintained correspondingly. Hidden Suffix Links There is another special case which is incurred by problem 1 and problem 2. Sometimes we need to hop over several nodes to the right point for split, we might surpass the right point if we move by comparing the remainder string and the path labels. That case the suffix link will be neglected unintentionally, if there should be any. This could be avoided by remembering the right point when moving forward. The suffix link should be maintained if the split node already exists, or even the problem 1 happens during a unfolding step.

最后，我在Python中的实现如下:

Python

提示:在上面的代码中包含了一个朴素的树打印函数，这在调试时非常重要。这帮我省了很多钱 时间短，便于定位特殊情况。

我的直觉如下:

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

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

在len(string)迭代之后，您将得到一个包含所有后缀的后缀树。

在循环过程中，关键是活动点。我的猜测是，这表示后缀树中最深的点，对应于字符串的前k个字符的适当后缀。(我认为合适的意思是后缀不能是整个字符串。)

例如，假设你见过字符'abcabc'。活动点将表示树中对应后缀'abc'的点。

活动点由(原点，第一个，最后一个)表示。 这意味着你目前在树中的点上，你可以从节点原点开始，然后输入字符串[first:last]中的字符。

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

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

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

注意3:封圣部分只是节省了检查活动点的时间。 例如，假设您总是使用origin=0，只是改变了第一个和最后一个。 为了检查活动点，您必须每次沿着所有中间节点跟随后缀树。 通过只记录到最后一个节点的距离来缓存遵循这条路径的结果是有意义的。

您能给出一个代码示例来说明“修复”边界变量是什么意思吗?

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

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

我发现之前回答的“规则”方法对理解潜在的原因没有帮助，所以我写了下面的所有内容，只关注语用学。如果你像我一样，对其他解释感到困惑，也许我的补充解释会让你“点击”。

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

请注意，我不是这方面的专家，所以以下部分可能包含不准确(或更糟)。如果你遇到任何问题，请随意编辑。

先决条件

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

(然而，我必须为流程添加一些基本的叙述，所以开头可能会让人觉得多余。)

最有趣的部分是解释了使用后缀链接和从根目录重新扫描之间的区别。这就是在我的实现中给我带来许多bug和头痛的原因。

开放式叶节点及其局限性

我相信你已经知道，最基本的“技巧”是意识到我们可以只留下后缀的结束“开放”，即引用字符串的当前长度，而不是将结束设置为一个静态值。这样，当我们添加额外的字符时，这些字符将隐式地添加到所有后缀标签中，而不必访问和更新所有这些字符。

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

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

例如，对于字符串'ABCXABCY'(见下文)，到X和Y的分支需要添加到三个不同的后缀ABC, BC和C;否则它就不是一个有效的后缀树，我们不能通过从根向下匹配字符来找到字符串的所有子字符串。

再次强调，我们对树中的后缀执行的任何操作都需要通过其连续的后缀反映出来(例如ABC > BC > C)，否则它们就不再是有效的后缀。

但是，即使我们接受我们必须进行这些手动更新，我们如何知道需要更新多少个后缀呢?因为，当我们添加重复字符A(以及其他连续重复字符)时，我们还不知道何时/何处需要将后缀分成两个分支。只有当我们遇到第一个非重复字符(在本例中是Y，而不是树中已经存在的X)时，才确定需要分割。

我们能做的是匹配最长的重复字符串，并计算后面需要更新的后缀的数量。这就是“余数”的含义。

“剩余”和“重新扫描”的概念

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

So, staying with the previous example of the string ABCXABCY, we match the repeated ABC part 'implicitly', incrementing remainder each time, which results in remainder of 3. Then we encounter the non-repeating character 'Y'. Here we split the previously added ABCX into ABC->X and ABC->Y. Then we decrement remainder from 3 to 2, because we already took care of the ABC branching. Now we repeat the operation by matching the last 2 characters – BC – from the root to reach the point where we need to split, and we split BCX too into BC->X and BC->Y. Again, we decrement remainder to 1, and repeat the operation; until the remainder is 0. Lastly, we need to add the current character (Y) itself to the root as well.

在Ukkonen的算法中，这个操作，从根开始，跟随连续的后缀到达我们需要做操作的点，这被称为“重新扫描”，通常这是算法中最昂贵的部分。想象一个更长的字符串，您需要跨几十个节点(我们将在后面讨论)“重新扫描”长子字符串，可能需要数千次。

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

后缀链接的概念

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

Of course one big question is how to add these links. The existing answer is that we can add the links when we insert new branch nodes, utilizing the fact that, in each extension of the tree, the branch nodes are naturally created one after another in the exact order we'd need to link them together. Though, we have to link from the last created branch node (the longest suffix) to the previously created one, so we need to cache the last we create, link that to the next one we create, and cache the newly created one.

一个后果是，我们实际上经常没有后缀链接，因为给定的分支节点刚刚创建。在这些情况下，我们仍然必须回到前面提到的“重新扫描”。这就是为什么在插入之后，会指示您使用后缀link或跳转到根目录。

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

“主动点”的概念

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

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

首先，我们总是位于节点的特定边缘，因此我们需要存储边缘信息。我们称之为“活动边”。

其次，即使在添加了边缘信息之后，我们仍然没有办法识别树中更下方的位置，并且不直接连接到根节点。所以我们也需要存储节点。我们称其为“活动节点”。

最后，我们可以注意到，“余数”不足以识别不直接连接到根结点的边上的位置，因为“余数”是整个路由的长度;我们可能不想麻烦地记住并减去之前的边的长度。所以我们需要一个表示就是当前这条边的余数。这就是我们所说的“活动长度”。

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

活动点=(活动节点，活动边，活动长度)

你可以在下图中观察到ABCABD的匹配路由是如何由边缘AB上的2个字符(从根开始)，加上边缘CABDABCABD上的4个字符(从节点4开始)组成的——结果是“剩余”6个字符。所以，我们当前的位置可以被识别为活动节点4，活动边C，活动长度4。

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

重新扫描和使用后缀链接的区别

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

考虑以下字符串'AAAABAAAABAAC'的例子:

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

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

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

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

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

考虑一下上面例子的下一步会发生什么。让我们比较一下如何实现相同的结果——即移动到下一个后缀来处理——使用和不使用后缀链接。

使用后缀link

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

在上面的例子中，由于“活动长度”是4，我们使用后缀“ABAA”，从链接的节点4开始。但在找到与后缀('A')的第一个字符对应的边后，我们注意到我们的“活动长度”超出了这条边3个字符。所以我们跳过整个边缘，跳转到下一个节点，并通过跳跃消耗的字符减少“活动长度”。

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

请注意，这个操作似乎通常不被称为“重新扫描”，尽管对我来说，它似乎直接等同于重新扫描，只是长度缩短了，起点不是根。

使用“重新扫描”

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

这个后缀的长度就是我们之前讨论过的“余数”。我们要消耗这个余数的全部，直到它为0。这可能(通常是这样)包括跳过多个节点，在每次跳跃时减少我们跳过的边的长度。最后，我们到达一条比剩下的“余数”更长的边;这里我们将活动边设置为给定的边，将“活动长度”设置为剩余的“余数”，然后我们就完成了。

但是请注意，需要保留实际的“余数”变量，并且只在每次插入节点后递减。所以我上面所描述的假设使用一个单独的变量初始化为'remainder'。

注意后缀链接和重新扫描

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

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

3) One important remark pertaining to performance is that there is no need to check each and every character during rescanning. Due to the way a valid suffix tree is built, we can safely assume that the characters match. So you're mostly counting the lengths, and the only need for character equivalence checking arises when we jump to a new edge, since edges are identified by their first character (which is always unique in the context of a given node). This means that 'rescanning' logic is different than full string matching logic (i.e. searching for a substring in the tree).

4)这里描述的原始后缀链接只是一种可能的方法。例如，NJ Larsson等人将这种方法命名为面向节点的自顶向下方法，并将其与面向节点的自底向上方法和两个面向边方法进行了比较。不同的方法有不同的典型和最坏情况的性能、需求、限制等，但通常情况下，面向边缘的方法似乎是对原始方法的全面改进。

嗨，我已经尝试在ruby中实现上述解释的实现，请检查它。 它似乎工作得很好。

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

它也出现在https://gist.github.com/suchitpuri/9304856

    require 'pry'


class Edge
    attr_accessor :data , :edges , :suffix_link
    def initialize data
        @data = data
        @edges = []
        @suffix_link = nil
    end

    def find_edge element
        self.edges.each do |edge|
            return edge if edge.data.start_with? element
        end
        return nil
    end
end

class SuffixTrees
    attr_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 = 1
    end

    def build string
        string.split("").each_with_index do |element , index|


            add_to_edges @root , element        

            update_pending_prefix element                           
            add_pending_elements_to_tree element
            active_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] = 0
            end
        end
    end

    def add_pending_elements_to_tree element

        to_be_deleted = []
        update_active_length = false
        # binding.pry
        if( @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 + 1
            return
        end



        @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].data
                data = data.split("")               

                location = @active_point[:active_length]


                # binding.pry
                if(data[0..location].join == pending_prefix or @active_point[:active_node].find_edge(element) != nil )                  


                else #tree split    
                    split_edge data , index , element
                end

            end
        end 
    end



    def update_pending_prefix element
        if @active_point[:active_edge] == nil
            @pending_prefixes = [element]
            return

        end

        @pending_prefixes = []

        length = @active_point[:active_edge].data.length
        data = @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 , element
        location = @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_edges
        end


        #setup the suffix link
        if @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 index
        if(@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])
        else
            if @active_point[:active_node].suffix_link != nil
                @active_point[:active_node] = @active_point[:active_node].suffix_link               
            else
                @active_point[:active_node] = @root
            end 
            @active_point[:active_edge] = @active_point[:active_node].find_edge(@active_point[:active_edge].data[0])
            @remainder = @remainder - 1     
        end
    end

    def add_to_edges root , element     
        return if root == nil
        root.data = root.data + element if(root.data and root.edges.size == 0)
        root.edges.each do |edge|
            add_to_edges edge , element
        end
    end
end

suffix_tree = SuffixTrees.new
suffix_tree.build("abcabxabcd")
binding.pry

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

使用的其他变量

活动点-一个三元(active_node;active_edge;Active_length)，显示我们必须从哪里开始插入新后缀。 剩余-显示必须显式添加的后缀的数量。例如，如果我们的单词是'abcaabca'，并且remainder = 3，这意味着我们必须处理3个最后的后缀:bca, ca和a。

让我们使用一个内部节点的概念——所有的节点，除了根节点和叶节点都是内部节点。

观察1

当我们发现需要插入的最后一个后缀已经存在于树中时，树本身根本不会改变(我们只更新活动点和余数)。

观察2

如果在某一点上active_length大于或等于当前边缘的长度(edge_length)，我们将活动点向下移动，直到edge_length严格大于active_length。

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

规则1

如果从活动节点= root插入后，活动长度大于0，则: 主节点未改变 活动长度减少 活动边向右移动(到必须插入的下一个后缀的第一个字符)

规则2

如果我们创建一个新的内部节点或从一个内部节点创建一个插入器，并且这不是当前步骤中的第一个此类内部节点，那么我们将通过后缀链接将前一个此类节点与this节点链接起来。

规则2的定义与jogojapan的不同，因为这里我们不仅考虑了新创建的内部节点，还考虑了我们进行插入的内部节点。

规则3

在从活动节点(不是根节点)进行插入之后，必须遵循后缀链接并将活动节点设置为它所指向的节点。如果没有后缀链路，请将主节点设置为根节点。无论哪种方式，活动边和活动长度保持不变。

在规则3的这个定义中，我们还考虑了叶节点的插入(不仅仅是分裂节点)。

最后，观察3:

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

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

如果我们不使用后缀link连接节点: 在加上最后一个字母c之前: 加上最后一个字母c后: 如果我们确实通过后缀link连接节点: 在加上最后一个字母c之前: 加上最后一个字母c后:

Seems like there is no significant difference: in the second case there are two more suffix links. But these suffix links are correct, and one of them - from the blue node to the red one - is very important for our approach with active point. The problem is that if we don't put a suffix link here, later, when we add some new letters to the tree, we might omit adding some nodes to the tree due to the Rule 3, because, according to it, if there's no a suffix link, then we must put the active_node to the root.

When we were adding the last letter to the tree, the red node had already existed before we made an insert from the blue node (the edge labled 'c'). As there was an insert from the blue node, we mark it as needing a suffix link. Then, relying on the active point approach, the active node was set to the red node. But we don't make an insert from the red node, as the letter 'c' is already on the edge. Does it mean that the blue node must be left without a suffix link? No, we must connect the blue node with the red one through a suffix link. Why is it correct? Because the active point approach guarantees that we get to a right place, i.e., to the next place where we must process an insert of a shorter suffix.

最后，这里是我对后缀树的实现:

Java c++

希望这个“概述”结合jogojapan的详细回答将帮助某人实现他自己的后缀树。