向后缀数组的更深一步探索:SA-IS

代码

最近训练发现字符串的题因为我太菜了几乎都做不出来,便打算重拾这个数据结构。

之前一直学的是倍增法,但是倍增O(nlogn)嘛。。emmm,怎么看都觉得会被卡XD

然鹅又听说过之前有过题目会卡O(n)的DC3而倍增却能过。。神奇

而SA-IS(Suffix Array-Induce Sort)是一个比DC3常数要小的O(n)计算后缀数组的算法

所以便开始了学习。。从两个星期前

这两个星期我浏览了很多文章,发现这些文章在某些重要的地方(比如给lms前缀排序就能推出lms子串的顺序)表述不清

甚至有的概念是冲突的(比如lms子串到底包不包含最后一个lms字符)

而且有的是英文文章,啃起来有点吃力

打算自己写个SA-IS教程了,因为我自己来说大体上还是把这个算法摸清了

咕咕咕,一定会写

下面先放两份代码吧,完全按照我自己的思路写的,用来记忆肯定是不够短小,其中一份在输出时会详细地介绍每个部分会做什么,希望各位能看的愉快。

带标注版本:https://paste.ubuntu.com/p/8zFGrcNfYS/

无标注版本:https://paste.ubuntu.com/p/zNBHB4TWS5/

对应洛谷模板题 P3809 https://www.luogu.org/problemnew/show/P3809

欢迎在评论区询问问题。(然鹅这个博客有人来过吗)

我还没有学会写个人说明!

发表评论

电子邮件地址不会被公开。 必填项已用*标注