后缀数组挺好玩的，于是来写后缀数组学习笔记了。
什么是后缀数组？
后缀数组主要关系到 2 个数组：\(sa\) 和 \(rk\)。
-
\(sa[i]\) 表示将所有后缀按照字典序从小到大排序，排名第 \(i\) 的后缀的开头为第 \(sa[i]\) 个字符。
-
\(rk[i]\) 表示将所有后缀按照字典序从小到大排序，后缀开头为第 \(rk[i]\) 个字符的排名。
接下来我们会简称后缀 \(i\) 为后缀开头为第 \(i\) 个字符的后缀。
这两个数组满足一个性质：\(sa[rk[i]]=rk[sa[i]]=i\)（请自行理解）。