【字符串】后缀数组

我的字符串全部都是下标从1开始的， 千万要小心。 字符串 \(s[1, n]\) 中，有 \(n\) 个后缀，他们分别是 \(s[1, n], s[2, n], s[3, n], ..., s[i, n], ..., s[n, n]\) 。 对这 \(n\) 个后缀进行排序，由于他们长度不同所以他们的排序结果一定是 \([1, n]\) 的一个排列，这个排列（rk数组）就称为后缀数组。

后缀数组表示为两个对应的数组，主要是sa，在下面有解释： \(sa[i]\) 排名为 \(i\) 的后缀的起始位置为sa[i]。 也就是说，在全部的n个后缀中，s[sa[1], n] 是其中字典序最小的后缀。通常，sa是被用来二分的对象，它是后缀数组本身。

\(rk[i]\) 起始位置为 \(i\) 的后缀，也就是s[i, n]的排名。rk是用来解决字符串被复制了一次之后，需要识别原串的情况使用的。

这两个数组满足性质 \(sa[rk[i]] = i, rk[sa[i]] = i\)

看图比较好直观理解：https://oi-wiki.org/string/sa/

用法简介： 求字符串S的某个子串或者反向子串是否相等或者比较大小：查询O(1) 求模式串出现的所有位置：后缀数组上二分然后暴力匹配，查询O(|T|log|S|) 求出现k次的子串：height数组上的连续k-1个位置的滑动窗口 互不相交的子串：求两个子串在后缀数组中的最小值和最大值，变成RMQ问题 本质不同的子串：去掉height数组中表示重复子串的LCP部分

\(n\) 字符串的长度。 \(m\) 当前后缀（离散化后）的值域。对于char可以跳过离散化，初值取128即可，对于int要离散化，初值取n即可，初值要保证覆盖整个值域。 \(sa[i]\) 排名为 \(i\) 的后缀的起始位置。也就是说，在全部的n个后缀中，s[sa[1], n] 是其中字典序最小的后缀。 \(rk[i]\) 起始位置为 \(i\) 的后缀的排名。

验证：https://www.luogu.com.cn/problem/P3809