什么是后缀数组
后缀数组主要是用来处理字符串的，分为两种方法：倍增法以及 DC3，但由于倍增法通俗易懂，码量小，常数小，所以今天这篇文章我就只介绍倍增法（不可能是因为我不会 DC3）
前缀知识
No.1 基数排序
跟桶排序差不了多少，思想就是：将整数按位数切割成不同的数字，然后按每个位数分别比较。按每个位数从低位数到高位数分别比较。
然后在后缀数组中，我们就借用了这个思想来处理一个二元组，这之后我们还会接着讲。
No.2 文章中的数组介绍
\(sa_i\)：排名为i的后缀的位置
\(rak_i\)：从第i个位置开始的后缀的排名，
下文为了叙述方便，把从第i个位置开
始的后缀简称为后缀i
\(tp_i\)：基数排序的第二关键字，意义与sa一样
，即第二关键字排名为i的后缀的位置
\(tag_i\)：i号元素出现了多少次。辅助基数排序。
标签：后缀,笔记,基数排序,位数,数组,SA,倍增,sa From： https://www.cnblogs.com/pdpdzaa/p/17436993.html