震惊！$0\%$的人都不知道，后缀数组还可以这样求……

继去年为大家带来树状数组黑科技讲义之后，今年带来全新的后缀数组黑科技讲义！

众所周知后缀数组有$O(n \log n)$的倍增方法以及$O(n)$的DC3方法。而本文将会简单介绍倍增方法并详细讲解黑科技: $O(n)$的SAM方法以及SA-IS方法。

食用本文前建议对后缀数组(SA)和后缀自动机(SAM)有基本了解。

详细内容欢迎大家访问我的博客: 求后缀数组的SAM与SA-IS方法。

已更新Ukkonen算法: Ukkonen算法与后缀树构造后缀数组。