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

之前一直学的是倍增法，但是倍增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

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