有人可以解释何时以及如何扩展后缀树？

Question

我正在寻找一个PHP脚本，它必须找到最长的重复子字符串。我发现了这个后缀树的东西。我试图实现Ukkonnen的算法，但是我无法得到何时以及如何扩展树。

没关系，如果我有新的charachter不在树中，但我必须从根创建一个新节点和egde。但是我应该怎么知道我是否需要分割边缘呢？我发现它的C++实现（link），我试图将它翻译成PHP，但我认为我有一个typeo，因为它提供了一个几乎好的结果，问题是我无法修复它直到我完全不了解它...

我读了十几种后缀树的描述，但其中一些描述并没有太深入，其他人在第二次见证后给我头痛。

这里是我现在的代码：Suffix-tree.php（对不起，但是这个编辑器拿不到）我用这个site来检查结果。

所以任何意见，将不胜感激......

编辑：我重写它提到的网站上找到的JavaScript代码块。这里是源代码的链接：Suffix-Tree v0.1

Answer 1

数据压缩专家Matt Mahoney给出了一个很好的解释。但是我也不了解实施情况，这很困难。仅供参考我已经设法运行后缀树php扩展。如果有帮助，你可以在sourceforge找到我的代码。我很想看到你的最终代码！