arrays - 使用 manber myers 算法的后缀数组

Question

我已经尝试过在论文http://webglimpse.net/pubs/suffix.pdf中的理论

但是当他们说我有点迷茫

令 Ai 为第一个桶中的第一个后缀（即 Pos[0] = i），并考虑 Ai-h（如果 ih < 0，那么我们忽略 Ai 并取 Pos[1] 的后缀，依此类推） . 由于 Ai 从最小的 h 符号字符串开始，Ai-h 应该是其 2h 桶中的第一个。

我无法理解这种说法。为什么如果 ih < 0 可以忽略 Ai-h。当阶段 1 中 ih > 0 时，如何在 const time 中确定位置？

一个示例 impl 是http://belbesy.wordpress.com/2012/10/10/spoj-649-distinct-substrings-suffix-arrays-nlgn/

Answer 1

我强烈建议不要尝试理解 C++ 代码，而是手动完成 Manbers-Myers 后缀数组构造算法的 Python 实现，以获取一个简单的 5 个字符示例。

因为 Python 版本只有大约 15 行代码，所以很容易理解。

即使你不懂 Python，也要把它当作伪代码，用 Google 搜索你不懂的语法。

就我个人而言，我手动遍历了一个 5 个字符的字符串，这足以帮助我理解算法的工作原理。