我正在寻找一种快速后缀阵列构造算法.我对实现的简易性和原始速度比渐近复杂度更感兴趣(我知道后缀数组可以在O(n)时间内通过后缀树构造,但是需要很多空间;显然其他算法都有糟糕的最糟糕的大O复杂性,但在实践中运行得相当快).我不介意生成LCP阵列作为副产品的算法,因为我无论如何都需要一个用于我自己的目的.
我找到了各种后缀数组构造算法的分类,但它已经过时了.我听说过SA-IS,qsufsort和BPR,但我真的不知道它们如何相互比较,也没有更好的算法.考虑到后缀阵列字段现在看起来有多热,我希望其他一些算法在发布之后已经取代了那些算法.我似乎回想起一篇描述一种叫做"分裂"的快速算法的论文,但我现在找不到它的生命.
那么,目前的艺术水平是什么？理想情况下,我想要一份当前最佳算法的简短列表(如果可能的话,还有链接)以及他们相对优势和劣势的快速概述.
suffix-array ×1