Tag: 后缀数组

什么是当前最新的后缀数组构造algorithm？

我正在寻找一个快速的后缀数组构造algorithm。 我对易于实现和原始速度比渐近复杂性更感兴趣（我知道在O（n）时间后缀数组可以通过后缀树来构造，但是需要很多空间;显然其他algorithm有坏的最坏的情况下，大O的复杂性，但在实践中跑得相当快）。 我不介意产生LCP数组作为副产品的algorithm，因为我为了自己的目的需要一个algorithm。 我发现了各种后缀数组构造algorithm的分类 ，但已经过时了。 我听说过SA-IS ， qsufsort和BPR ，但是我不知道它们是如何相互比较的，也没有更好的algorithm。 考虑到后缀数组字段看起来有多热，我期望其他一些algorithm已经取代了自发布以来的algorithm。 我似乎记得遇到一篇论文，描述了一种叫做“split”的快速algorithm，但现在我无法在我的生活中find它。 那么，现在的艺术状况如何呢？ 理想情况下，我希望列出当前最好的algorithm（如有可能，请链接），并简要概述其优缺点。

后缀数组algorithm

在阅读了一段时间之后，我已经想出了一个后缀数组和LCP数组代表了什么。 后缀数组 ：表示数组中每个后缀的_lexicographic等级。 LCP数组 ：包含两个连续后缀之间的最大长度前缀匹配， 按照字典顺序sorting 。 我已经努力了解了几天， 后缀数组和LCPalgorithm的工作原理。 这是从Codeforces获取的代码： /* Suffix array O(n lg^2 n) LCP table O(n) */ #include <cstdio> #include <algorithm> #include <cstring> using namespace std; #define REP(i, n) for (int i = 0; i < (int)(n); ++i) namespace SuffixArray { const int MAXN = 1 << 21; char * S; int […]