前言
先把 SA 给写出来，SAM 暂时还没学会，学会了应该也不会写，因为构造过程过于繁琐。
本文可能对 SA 的算法流程和代码实现上的介绍相对简略，主要介绍一些常见用途。
约定
- 无特殊说明字符串的下标从 \(1\) 开始。
- 无特殊说明 \(s\) 表示字符串，\(n\) 表示字符串长度。
- “后缀 \(i\)”或“第 \(i\) 个”后缀指字符串从第 \(i\) 个字符开始的后缀。
- \(s[l,r]\) 表示字符串 \(s\) 第 \(l\) 到第 \(r\) 个字符构成的子串。
用途
后缀数组最主要的用途就是进行后缀排序，也就是将一个字符串的 \(n\) 个后缀以 \(O(n\log n)\) 的复杂度按照字典序进行排序（一般为升序），可以帮我们求出来三个数组：
- \(sa[i]\)：后缀排序后排名第 \(i\) 的后缀的编号。
- \(rk[i]\)：第 \(i\) 个后缀进行排序后的排名。
- \(height[i]\)：排第 \(i\) 的后缀与排第 \(i-1\) 名的后缀的 \(lcp\)（最长公共前缀）长度，特别地 \(height[1]=0\)。
利用排序后后缀间的一些性质，我们可以解决许多字符串相关的问题。
算法流程
首先考虑最暴力的想法：直接将字符串的 \(n\) 个后缀都拉出来，然后直接对他们跑 sort。
由于字符串比较字段序是 \(O(n)\) 的，所以最坏时间复杂度为 \(O(n^2\log n)\)。
由于太唐了，这里不多叙述。
倍增
考虑优化这个过程，这里需要用到一个倍增的思想。
我们先不着急对后缀进行排序，而是先对 \(s\) 所有大小为 \(k\) 的子串进行排序，大概是如下的流程：
- 最开始时，我们令 \(k=1\)，即对所有大小为 \(1\) 的子串排序，记 \(rk_{1,i}\) 为此轮排序的结果。
- 随后，令 \(k=k\times 2\)，现在要对所有长为 \(k=2\) 的子串排序，此时可以直接采用双关键字排序：对每个长度为 \(2\) 的子串分别设定 \(rk_{1,i}\) 和 \(rk_{1,i+1}\) 为其第一二关键字。然后再直接跑
sort，就可以得到所有长度为 \(2\) 的子串排序的结果，同样记 \(rk_{4,i}\) 为本轮排序结果。 - 再令 \(k=k\times 2\)，现在对所有长度为 \(4\) 的子串排序，同样直接以 \(rk_{2,i}\) 和 \(rk_{2,i+2}\) 为关键字
sort即可，本轮排序结果为 \(rk_{4,i}\)。 - 继续重复上面的过程，直到 \(k\ge n\) 算法结束。
对于 \(i+k/2>n\) 的情况，我们直接令其第二关键字为 \(0\)（最小的）即可。
这样我们 \(k\) 倍增 \(\log n\) 轮之后就会不小于 \(n\)，每轮使用 sort 排序的复杂度为 \(O(n\log n)\)，因此总复杂度 \(O(n\log^2 n)\)。
（图片来源于 OI-Wiki，仅帮助理解使用）
由于这里懒得自己写一份，同样给一个 OI-Wiki 上的代码实现：
char s[N];
int n, w, sa[N], rk[N << 1], oldrk[N << 1];
int main() {
int i, p;
scanf("%s", s + 1);
n = strlen(s + 1);
for (i = 1; i <= n; ++i) sa[i] = i, rk[i] = s[i];
for (w = 1; w < n; w <<= 1) {
sort(sa + 1, sa + n + 1, [](int x, int y) {
return rk[x] == rk[y] ? rk[x + w] < rk[y + w] : rk[x] < rk[y];
});
memcpy(oldrk, rk, sizeof(rk));
// 由于计算 rk 的时候原来的 rk 会被覆盖，要先复制一份
for (p = 0, i = 1; i <= n; ++i) {
if (oldrk[sa[i]] == oldrk[sa[i - 1]] &&
oldrk[sa[i] + w] == oldrk[sa[i - 1] + w]) {
rk[sa[i]] = p;
} else {
rk[sa[i]] = ++p;
} // 若两个子串相同，它们对应的 rk 也需要相同，所以要去重
}
}
for (i = 1; i <= n; ++i) printf("%d ", sa[i]);
return 0;
}
基数排序
其实还可以在进一步，如果有 \(O(n)\) 排序的方法，那么整个算法的复杂度就可以降到 \(O(n\log n)\) 了。
有没有呢？当然有，直接使用基数排序就可以把每轮的排序过程优化到线性。
当然这里是双关键字排序，可以先按照第二关键字做一遍排序，然后在此基础上按第一关键字排序，就可以达到想要的双关键字排序的效果了。
基数排序这里不多讲了，感觉能理解桶排肯定就能懂基排吧……
实现细节
相信读者完全理解上文后其实已经能够自己实现出 \(O(n\log n)\) 的后缀排序了，但是这里还是要多说一点实现部分，因为直接完全按照上面的做法写会常数巨大，下面会介绍一些优化方式。
首先直接给出来我自己的后缀排序代码：
#include<bits/stdc++.h>
#define For(i, a, b) for(int i = (a); i <= (b); i++)
#define Rof(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
int n, m, sa[1000005], cnt[1000005], rk[1000005], tmp[1000005];
char s[1000005];
void get_SA(){
n = strlen(s + 1); m = 122;
For(i, 1, n) cnt[rk[i] = s[i]]++;
For(i, 1, m) cnt[i] += cnt[i - 1];
Rof(i, n, 1) sa[cnt[rk[i]]--] = i;
for(int k = 1; k <= n; k <<= 1){
int tot = 0;
For(i, n - k + 1, n) tmp[++tot] = i;
For(i, 1, n) if(sa[i] > k) tmp[++tot] = sa[i] - k;
For(i, 1, m) cnt[i] = 0;
For(i, 1, n) cnt[rk[tmp[i]]]++;
For(i, 1, m) cnt[i] += cnt[i - 1];
Rof(i, n, 1) sa[cnt[rk[tmp[i]]]--] = tmp[i];
swap(rk, tmp); rk[sa[1]] = tot = 1;
auto check = [&](int x, int y, int w){
return tmp[sa[x]] == tmp[sa[y]] && tmp[sa[x] + k] == tmp[sa[y] + k];
};
For(i, 2, n) rk[sa[i]] = check(i, i - 1, k) ? tot : ++tot;
if(n == tot) break; m = tot;
}
}
void Solve(){
cin >> (s + 1); get_SA();
For(i, 1, n) cout << sa[i] << ' ';
}
优化 1：第二关键字的基数排序可以省去
仔细思考对第二关键字排序的过程，不难发现实质上是将长度在 \(k/2\) 内的后缀（也就是第二关键字不存在）排到最前面，存在第二关键字时直接将上轮排序结果按顺序放入就好了。
体现在代码里的是这两行：
For(i, n - k + 1, n) tmp[++tot] = i; //不存在当然是最小
For(i, 1, n) if(sa[i] > k) tmp[++tot] = sa[i] - k; //其余顺次放入，注意这里有个 -k，因为再往前移 k 位的那个后缀是把自己当第二关键字的
优化 2：实时更新桶的值域上限
代码中的 \(m\) 记录的是能放入桶中的数最大为多少，每次给桶清零和做前缀和时只需枚举到 \(m\) 即可。
优化 3：所有子串排名不同时及时结束
注意到字典序是从前往后比的，如果出现某一轮要排序的 \(n\) 个子串排名已经完全区分开，那么再往后加入字符字典序大小关系显然不会变，此时就已经得到最终的排序结果了，直接退出即可。
在代码中也就是检查 \(m\) 和 \(tot\) 是否相等的那一小句。
height 数组
注意到我们开局提到的三个数组目前只求了两个，还有剩下 \(height\)。
记 \(lcp(i,j)\) 表示后缀 \(i\) 与后缀 \(j\) 之间的最长公共前缀的长度，回顾下 \(height\) 数组的定义，\(height[i]\) 实际上表示的就是 \(lcp(sa[i],sa[i-1])\)。
引理：\(height[rk[i]]\ge height[rk[i-1]]-1\)。
具体证明我不太会，但是感性理解是容易的。
有了上面这个引理可以直接暴力求，因为每次只减 \(1\) 所以总复杂度是 \(O(n)\) 的。
void get_height(){
for(int i = 1, k = 0; i <= n; i++){
if(rk[i] == 1) continue;
int j = sa[rk[i] - 1];
if(k) k--;
while(s[i + k] == s[j + k] && max(i + k, j + k) <= n) k++;
height[rk[i]] = k;
}
}
经典应用
讲完了整个后缀数组的构建过程，我们就要介绍一些经典用法了。
求任意两个后缀 \(lcp\)
对于任意两个后缀 \(i,j\)，设 \(rk[i]<rk[j]\)，有
\[lcp(i,j)=\min_{k=rk[i]+1}^{rk[j]}height[k] \]显然，如果 \(height\) 一直大于某个数，那么前几位就一直没变过；反之，由于后缀已经排好序了，不可能变了之后变回来
可以使用 ST 表做到 \(O(n\log n)-O(1)\)。
比较任意两个子串字典序
假如我们要比较 \(s[l_1,r_1]\) 和 \(s[l_2,r_2]\) 的大小：
- 如果 \(lcp(l_1,l_2)\ge\max(r_1-l_1+1,r_2-l_2+1)\)，等价于比较两者的长度。
- 否则等价于比较 \(rk_{l_1}\) 和 \(rk_{l_2}\)。
求不同子串数目
不同指长得不同。
考虑用子串个数减去重复个数，后缀排序后相邻两个后缀之间会贡献 \(height[i]\) 个相同子串，因此答案为
\[\frac{n(n+1)}{2}-\sum_{i=2}^nheight[i] \]求任意子串出现次数
假设我们要查询 \(s[l,r]\) 在 \(s\) 中的出现次数。
一个在字符串问题中的常用思考方式：子串是后缀的前缀。
\(s[l,r]\) 显然是后缀 \(l\) 的一段前缀，如果 \(s[l,r]\) 出现了多次，那它应该还是其他一些后缀的前缀，而这些后缀因为有公共前缀在后缀排序后应该是一段连续的区间，因此我们直接从 \(height[rk[l]]\) 向两边扩展，扩展的过程中保证 \(lcp\) 不小于 \(r-l+1\) 即可。
可以使用 ST 表维护，每次查询二分，做到 \(O(n\log n)-O(\log n)\)。
给一份示范代码：
void init(){
get_SA(); get_Height();
For(i, 2, n) lg[i] = lg[i >> 1] + 1;
For(i, 1, n) st[0][i] = height[i];
For(i, 1, 19) For(j, 1, n)
st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
}
int query(int l, int r){
int k = lg[r - l + 1];
return min(st[k][l], st[k][r - (1 << k) + 1]);
}
int get_cnt(int L, int R){ //s[l...r] 出现次数
if(!(1 <= L && L <= R && R <= n)) return 0;
int len = R - L + 1, pos = rk[L], res = 1;
int l = 1, r = pos - 1, ans = pos;
while(l <= r){
int mid = (l + r) >> 1;
if(query(mid + 1, pos) >= len) r = mid - 1, ans = mid;
else l = mid + 1;
}
res += pos - ans;
l = pos + 1, r = n, ans = pos;
while(l <= r){
int mid = (l + r) >> 1;
if(query(pos + 1, mid) >= len) l = mid + 1, ans = mid;
else r = mid - 1;
}
res += ans - pos;
return res * (R - L + 1);
}
未完待续……
标签：子串,后缀,笔记,height,SA,排序,sa,rk From： https://www.cnblogs.com/los114514/p/18021863