简单英语中的Ukkonen后缀树算法

Question

简单英语中的Ukkonen后缀树算法在这一点上我觉得有点厚。我花了几天的时间试图把我的头完全集中在后缀树的构造上，但由于我没有数学背景，所以很多解释都没有得到解释，因为它们开始过度使用数学符号。我发现最接近正确解释的是带后缀树的快速字符串搜索，但他掩盖了不同的点和一些方面的算法仍然不清楚。我确信，在堆栈溢出的情况下，一步地解释这个算法对于除我之外的其他许多人来说都是非常宝贵的。作为参考，以下是Ukkonen关于该算法的论文：http：/www.cs.helsinki.fi/u/Ukkonen/SuffixT1withFigs.pdf到目前为止，我的基本理解是：我需要遍历给定字符串T的每个前缀P我需要遍历前缀P中的每个后缀S并将其添加到树中要向树中添加后缀S，我需要遍历S中的每个字符，迭代包括沿着现有的分支遍历，该分支以S中的同一组字符C开头，当我到达后缀中的不同字符时，可能会将边分割为后代节点，或者如果没有匹配的边向下行走。当C没有找到匹配的边时，就会为C创建一个新的叶子边缘。基本算法似乎是O(N)2)，正如在大多数解释中所指出的那样，由于我们需要遍历所有前缀，那么我们需要遍历每个前缀的每个后缀。Ukkonen的算法显然是独一无二的，因为他使用了后缀指针技术，尽管我认为那，那个我很难理解。我也很难理解：指定、使用和更改“活动点”的确切时间和方式算法的经典方面是怎么回事？为什么我看到的实现需要“修复”他们使用的边界变量这是已完成的C#源代码。它不仅工作正常，而且支持自动封圣，并呈现出更好看的输出文本图。源代码和示例输出位于：https://gist.github.com/2373868更新2017-11-04许多年后，我发现了后缀树的新用法，并在JavaScript..盖斯特在下面。应该没有窃听器。把它倒入一个js文件，npm install chalk在相同的位置运行node.js，可以看到一些丰富多彩的输出。在同一个Gist中有一个简化版本，没有任何调试代码。https：/gist.github.com/axe蛙/c347bf0f5e0723cbd09b1aed6ec6fc6