Tag: 后缀树

在使用后缀树的string中最长的回文

我试图find一个string中最长的回文。 powershell解决scheme需要O（n ^ 3）时间。 我读了使用后缀树有一个线性时间algorithm。 我熟悉后缀树，并且很舒适地构build它们。 你如何使用内置的后缀树find最长的回文。

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

这一点我感觉有点厚。 我已经花了好几天的时间想把自己的头完全包裹在后缀树的构造中，但是因为我没有数学背景，所以很多的解释都是在我开始过度使用数学符号的时候解决的。 最接近我找到的一个很好的解释是使用后缀树的快速字符串搜索 ，但是他掩盖了不同的点，算法的某些方面仍然不清楚。 我相信，在这里Stack Overflow的这个算法的一步一步的解释对于除了我之外的其他许多人来说是非常宝贵的。 作为参考，这里是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中实现了这个算法。 Gist在下面。 它应该是无bug的。 将其转储到一个js文件中， npm install chalk从相同位置npm install chalk ，然后使用node.js运行以查看一些丰富多彩的输出。 在同一个Gist中有一个精简的版本，没有任何的调试代码。 https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6