java – 后缀数组nlogn的创建

发布时间：2020-12-14 17:41:22 所属栏目：Java 来源：网络整理

导读：我一直在学习 suffix arrays创作,我明白,我们首先根据第一个字符排序所有的后缀,然后根据前2个字符,然后是前4个字符等等,而要考虑的字符数小于2n. 但我的怀疑是为什么我们不选择前3个字符,然后9 …等等.为什么只考虑2个字符,因为这些字符串是相同字符串的一

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

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

我还没有彻底地分析后缀数组构造算法,但还是想分享一下我的想法.

在我看来,你的问题类似于以下几点：

>为什么计算机使用信息的二进制编码而不是三进制？
>为什么二进制搜索将对齐区分为三分之一？
>为什么有两性而不是三性？

原因是数字2是特殊的 – 它是最小的复数. 1和2之间的差异是定性的,而2和3之间的差异(以及任何其他正整数)是定量的,因此不是剧烈的.

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!