前置知识：后缀数组
参考链接：
https://blog.csdn.net/u013371163/article/details/60469533
https://www.bilibili.com/video/BV1sb411t79N?from=search&seid=13723955058308401416
http://www.cppblog.com/superKiki/archive/2010/05/15/115421.aspx
https://blog.csdn.net/the_ZED/article/details/105796444
后缀：Suffix(i)是指从位置i到字符串S末尾的串
后缀数组SA[i]：SA[i]存储的是第i大的后缀字符串在后缀中的下标【也可以说是 后缀排序后，从小到大每个后缀第一个字符在S中的位子（这个位子代表了它是第几个字符串）。】
名次数组rank[i]：rank[i]存储的是Suffix(i)在后缀中的排名
height[i]：存储Suffix(SA[i])和比Suffix(SA[i]-1)的最长公共前缀的长度。即排名相邻的两个后缀的最长公共前缀。
【sa[i]：第i大的是谁。rank[i]：串i是第几大的。】
构造sa数组：
以字符串S=“aabaaaaba”对应下标为012345678
DC3算法 复杂度时间复杂度On 空间复杂度On
一、把后缀分为两部分，然后对第一部分的后缀排序
将下标%3不等于0的分为一部分 1 2 4 5 7 8
将下标%3等于0的分为另一部分 0 3 6
然后对1 2 4 5 7 8进行排序
然后把下标1、2对应的后缀各自补成个数为3的倍数的串
aba aaa ba0
baa aab a00
然后每三个一组看，发现aba baa aaa aab ba0 a00是1 2 4 5 7 8开头的数据
接下来对前三个字母进行On桶排序
二、利用一中的结果，对第二部分的后缀排序
即对 0 3 6 进行排序
s[0]=x[0]+s[1];
s[3]=x[3]+s[4];
s[6]=x[6]+s[7];
三、将一二结果合并，完成排序
把3 0 6
和8 4 5 1 2 合并
标签：下标,Suffix,后缀,蓝桥,WYF,数组,SA,排序 From： https://www.cnblogs.com/ReflexFox/p/14617978.html