后缀数组

重学后缀数组 — LOJ 2122 「NOI2015」品酒大会

2020年7月20日2020年12月16日 by woshiluo

jt 学长说的没错，SA 果然是写一次忘一次……

于是这次重新学了一次，发现之前的 Blog 问题比较多，于是重写一次算了

实际上这些东西就是变相重写 Oi Wiki 后缀数组那一页，不过是写给自己的罢了

2019年5月8日2019年5月8日 by woshiluo

题目链接: https://www.luogu.org/problemnew/show/P3809

后缀数组用于解决各种玄学字符串问题，准确来说，它是一种思想

基于后缀数组有很多好玩毒瘤的东西

目前已知的求后缀数组的方法有

倍增法 (本博客所讲述) — $O(n \log(n))$
DC3 — $O(n)$
- DC3 虽然从复杂度分析的角度而言比倍增快，但配合各种常数问题，在信息学竞赛中反而容易被卡……
SA – IS 算法 — $O(n)$
- 可以参考这篇 Luogu 日报: https://www.luogu.org/blog/ShadowassIIXVIIIIV/on-hou-zhui-shuo-zu-sa-is-suan-fa

因为我太菜了，所以我就讲倍增求法