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 […]