use*_*192 10 java algorithm suffix-array suffix
我一直在学习后缀数组的创建,我明白我们首先按照第一个字符对所有后缀进行排序,然后根据前2个字符,然后是前4个字符,依此类推,同时要考虑的字符数小于2n.
但我怀疑的是为什么我们不选择前3个字符,然后是9 ......等等.为什么只考虑2个字符,因为字符串是相同字符串的一部分而不是不同的随机字符串？
我没有彻底分析后缀数组构造算法,但仍想分享我的想法.
在我看来,你的问题类似于以下问题:
为什么计算机使用信息的二进制编码而不是三元？
为什么二分搜索会将范围平分而不是将其三分为二？
为什么有两个性别而不是三个？
原因是数字2是特殊的 - 它是最小的复数.1和2之间的差异是定性的,而2和3之间的差异(以及任何其他正整数)是定量的,因此不是那么激烈.
结果,许多算法和数据结构的二进制公式被证明是最简单的,但是对于任意基础,它们中的一些可以被概括,具有不同程度的增加的复杂性.