前言 ：Orz ShichengXiao 冬令营的时候就早解决了
字符串算法还是不能随意放弃啊 要认真学了！！
这个算法常用于解决字符串上的 \(\mathrm{LCP}\) 问题 和 一些字符串匹配的问题
这个算法思维难度不是很大 但是代码难度还是有一些的
想学好这个算法 一定要牢牢的记住各个数组的含义 不然容易弄混
还是先简单介绍一下原理吧 ：
后缀数组就是将一个字符串的后缀全部进行排序 然后把下标存入一些数组里
用那些数组来进行字符串的一些常用操作
为了后缀排序 我们常常使用 \(O(n \log n)\) 的倍增算法
（而不用 \(O(n)\) 的 \(\mathrm{DC3}\) 因为它常数和空间大，并且十分不好写）
那接下来介绍一下倍增算法qwq
考虑这样一个小问题 我们比较任意两后缀的字典序大小 有没有什么快速比较的方法？
当然有 就是预处理出他们的一个前缀和后缀的大小关系 然后我们就能用另外两个来比较了。
倍增的思路大概就是如此 我们从小到大 每次长度乘二 排序长度是那些的后缀 然后用之前得到的信息去比较就行了。
具体就是变成双关键字排序，第一关键字就是前半部分的排名，第二关键字就是后半部分的排名。
这个东西套上基数排序就能优化一个 \(\log\) 。（基数排序具体见网上讲解吧qwq）
基数排序：我理解的就是 类似于桶排 我们开个桶来标记一下他们出现的次数
然后几个前缀和 那么这个数组的值就是他的排名 （可以模拟一下）
然后要满足双关键字 那么我们如果有几个元素第一关键字相同 它们在同一个下标上
那么我们就使第二关键字较大的先获得排名 其他的排名就比他小了。
具体实现见程序中的 Radix_Sort 就行了。
然后大概原理就是这样咯qwq （没讲清的话。。请去看看 刘汝佳的《算法竞赛入门经典》）
然后我介绍一下等下要出没的数组含义（很重要！！）
\(str[i]\) 表示 \(i\) 这个位置上的字符；
\(sa[i]\) 表示 后缀排序后第 \(i\) 名后缀的起始点下标；
\(rk[i]\) 表示 \(i\) 为起始点下标的后缀的排名；
\(tmp[i]\) 表示 \(i\) 的第二关键字排名 （在 \(swap\) 后作为第一关键字）
\(c[i]\) 表示在基数排序中在字符集中编号为 \(i\) 的出现次数（后面作为前缀和）、
还有两个变量 ： \(n\) 为字符串长度 \(m\) 为字符集大小
然后这样就可以直接做后缀排序了
代码中有详细解释 可以看看
int sa[N], tmp[N], c[N], rk[N], m, n; char str[N]; inline void Radix_Sort() { For (i, 1, m) c[i] = 0; //清空 For (i, 1, n) ++ c[rk[i]]; //先标记一下 此时 rk 是第一关键字 For (i, 1, m) c[i] += c[i - 1]; //记前缀和 Fordown(i, n, 1) sa[c[rk[tmp[i]]] --] = tmp[i]; //得到当前的 sa 数组，第二关键字 tmp 大的先得到更大的排名 } inline void Build_Sa() { For (i, 1, n) rk[i] = str[i], tmp[i] = i; m = 255; Radix_Sort(); //简单的初始化 for (register int k = 1, p; k <= n; k <<= 1) { //开始倍增 p = 0; For (i, n - k + 1, n) tmp[++ p] = i; //后 k 个的第二关键字为空 所以是最大的 For (i, 1, n) if (sa[i] > k) tmp[++ p] = sa[i] - k; //前面的话 只有 sa > k 的 sa 作为它前第 k 个第二关键字 Radix_Sort(); swap(rk, tmp); //基数排序，然后交换两个关键字 rk[sa[1]] = 1, m = 1; //初始化 For (i, 2, n) rk[sa[i]] = (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + k] == tmp[sa[i - 1] + k]) ? m : ++ m; //重新得到 rk 双关键字相同的 rk 一样 if (m >= n) return ; //如果当前排名两两不同就可以终止了 } }