java - 后缀数组nlogn创建

Question

我一直在学习suffix arrays创建，&我明白我们首先根据第一个字符对所有后缀进行排序，然后根据前 2 个字符，然后是前 4 个字符等等，而要考虑的字符数小于 2n。

但我的疑惑是为什么我们不选择前 3 个字符，然后是 9...等等。为什么只考虑 2 个字符，因为字符串是相同字符串的一部分而不是不同的随机字符串？

Answer 1

后缀数组构造算法我还没有分析透彻，还是想分享一下自己的想法。

依我愚见，您的问题与以下问题类似:

• 为什么计算机对信息使用二进制而不是三进制编码？

• 为什么二分搜索将范围一分为二而不是三等分？

• 为什么有两种性别而不是三种？

原因是数字 2 很特殊——它是最小的复数。 1 和 2 之间的差异是定性的，而 2 和 3(以及任何其他正整数)之间的差异是定量的，因此没有那么剧烈。

结果，许多算法和数据结构的二进制公式被证明是最简单的，尽管其中一些可能被推广，具有不同程度的增加复杂性，用于任意基础。