后缀数组详解
什么是后缀数组
后缀数组是处理字符串的有力工具 —罗穗骞
个人理解：后缀数组是让人蒙逼的有力工具！
就像上面那位大神所说的，后缀数组可以解决很多关于字符串的问题，
譬如这道题
注意：后缀数组并不是一种算法，而是一种思想。
实现它的方法主要有两种：倍增法O(nlogn)和 DC3法O(n)
其中倍增法除了仅仅在时间复杂度上不占优势之外，其他的方面例如编程难度，空间复杂度，常数等都秒杀DC3法
我的建议：深入理解倍增法，并能熟练运用（起码8分钟内写出来&&没有错误）。DC3法只做了解，吸取其中的精髓；
但是由于本人太辣鸡啦，所以本文只讨论倍增法
前置知识
后缀
这个大家应该都懂吧。。
比如说aabaaaab
它的后缀为
基数排序
我下面会详细讲
现在，你可以简单的理解为
基数排序在后缀数组中可以在O(n)的时间内对一个二元组(p,q)进行排序，其中p是第一关键字，q是第二关键字
比其他的排序算法都要优越
倍增法
首先定义一坨变量
sa[i]：排名为i的后缀的位置
rak[i]：从第i个位置开始的后缀的排名，下文为了叙述方便，把从第i个位置开始的后缀简称为后缀i
tp[i]：基数排序的第二关键字，意义与sa一样
tax[i]：i号元素出现了多少次。辅助基数排序
s[i]：字符串
可能大家觉得sa和rak这两个数组比较绕，没关系，多琢磨一下就好
事实上，也正是因为这样，才使得两个数组可以在O(n)的时间内互相推出来
具体一点
rak[sa[i]]=i
sa[rak[i]]=i
那我们怎么对所有的后缀进行排序呢？
我们把每个后缀分开来看。
开始时，每个后缀的第一个字母的大小是能确定的，也就是他本身的ASCLL值
具体点？把第$i$个字母看做是$(s[i],i)$的二元组，对其进行基数排序
这样我们就得到了他们的在完成第一个字母的排序之后的相对位置关系
接下来呢？
不要忘了， 我们算法的名称叫做“倍增法”，每次将排序长度*2，最多需要log(n)次便可以完成排序
因此我们现在需要对每个后缀的前两个字母进行排序
此时第一个字母的相对关系我们已经知道了。
那第二个字母的大小呢？我们还需要一次排序么？
其实大可不必，因为我们忽略了一个非常重要的性质：第i个后缀的第二个字母，实际是第i+1个后缀的第一个字母
因此每个后缀的第二个字母的相对位置关系我们也是知道的。
我们用tp这个数组把他记录出来，对(rak,tp)这个二元组进行基数排序
接下来我们需要对每个后缀的前四个字母组成的字符串进行排序
此时我们已经知道了每个后缀前两个字母的排名，而第i个后缀的第3,4个字母恰好是第i+2个后缀的前两个字母。
他们的相对位置我们又知道啦。
这样不断排下去，最后就可以完成排序啦
我相信大家看到这里肯定是一脸mengbi
下面我结合代码和具体的排序过程给大家演示一下
过程详解
还是以上面的图片为例
按照上面说的，开始时rak为字符的ASCLL码，第二关键字为它们的相对位置关系
这里的a数组是字符串数组
然后我们对其进行排序，我们暂且先不管它是如何进行排序，因为排序的过程非常难理解，一会儿我重点讲一下。
排完序之后各个后缀的位置关系是这样的
各个数组的大小
然后我们进行倍增。
这里再定义几个变量
M：字符集的大小，基数排序时会用到。不理解也没关系
p：排名的多少(有几个不同的后缀)
注意在排序的过程中，各个后缀的排名可能是相同的。因为我们在倍增的过程中只是对其前几个字符进行排名。
但是，对于每个后缀来说，最终的排名一定是不同的！毕竟每个后缀的长度都不相同
下面是倍增的过程
w表示倍增的长度，当各个排名都不相同时，我们便可以退出循环。
M=p是对基数排序的优化，因为字符集大小就是排名的个数
这两句话是对第二关键字进行排序
此时的p并不是统计排名的个数，只是一个简单的计数器
注意：有一些后缀是没有第二关键字的，他们的排名应该在最前面。
这对应第35行，不要忘了tp[i]的含义：排名为i的后缀的位置
注意第36行：如果sa[i]位置的后缀的第一关键字排名靠前，实际上代表着sa[i]-1位置的后缀的第二关键字排名靠前（比较难理解，大家好好琢磨一下）
此时第一二关键字都已经处理好了，我们进行排序
排完序之后，我们得到了一个新的sa数组
此时我们用sa数组来更新rak数组
我们前面说过rak数组是可能会重复的，所以我们此时用p来表示到底出现了几个名次
还需要注意一个事情，在判断是否重复的时候，我们需要用到上一轮的rak
而此时tp数组是没有用的，所以我们直接交换tp和rak
当然你也可以写为
在判断重复的时候，我们实际上是对一个二元组进行比较。
当满足判断条件时，两个后缀的名次一定是相同的（想一想，为什么？）
然后愉快的输出就可以啦！
放一下代码
// luogu-judger-enable-o2
#include<cstring>
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=1e6+10;
int sa[MAXN],tax[MAXN],rak[MAXN],tp[MAXN],a[MAXN],N,M;
char s[MAXN];
void debug()
{
printf("*****************\n");
printf("下标");for(int i=1;i<=N;i++) printf("%d ",i);printf("\n");
printf("sa ");for(int i=1;i<=N;i++) printf("%d ",sa[i]);printf("\n");
printf("rak ");for(int i=1;i<=N;i++) printf("%d ",rak[i]);printf("\n");
printf("tp ");for(int i=1;i<=N;i++) printf("%d ",tp[i]);printf("\n");
}
void Qsort()
{
for(int i=0;i<=M;i++) tax[i]=0;
for(int i=1;i<=N;i++) tax[rak[i]]++;
for(int i=1;i<=M;i++) tax[i]+=tax[i-1];
for(int i=N;i>=1;i--) sa[ tax[rak[tp[i]]]-- ]=tp[i];
}
void Ssort()
{
M=127;
for(int i=1;i<=N;i++)
rak[i]=a[i],tp[i]=i;
Qsort();
debug();
for(int w=1,p=1; p<N ; M=p,w<<=1)
{
p=0;
for(int i=1;i<=w;i++) tp[++p]=N-w+i;
for(int i=1;i<=N;i++) if(sa[i]>w) tp[++p]=sa[i]-w;
Qsort();
swap(rak,tp);
rak[sa[1]]=p=1;
for(int i=2;i<=N;i++)
rak[sa[i]]=(tp[sa[i-1]]==tp[sa[i]]&&tp[sa[i-1]+w]==tp[sa[i]+w])?p:++p;
debug();
}
for(int i=1;i<=N;i++) printf("%d ",sa[i]);
}
int main()
{
#ifdef WIN32
freopen("a.in","r",stdin);
#else
#endif
scanf("%s",s);
N=strlen(s);
for(int i=0;i<N;i++) a[i+1]=s[i]-48;
Ssort();
}再补一下调试结果
基数排序
如果你对上面的主体过程有了大致的了解，那么基数排序的过程就不难理解了
在阅读下面内容之前，我希望大家能初步了解一下基数排序
https://baike.baidu.com/item/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F/7875498?fr=aladdin
大致看一下它给出的例子和c++代码就好
先来大致看一下，代码就4行
M：字符集的大小，一共需要多少个桶
tax：元素出现的次数，在这里就是名次出现的次数
第一行：把桶清零
第二行：统计每个名词出现的次数
第三行：做个前缀和（啪，废话）
可能大家会疑惑前缀和有什么用？
利用前缀和可以快速的定位出每个位置应有的排名
具体的来说，前缀和可以统计比当前名次小的元素有多少个。
懒得举例子啦，不懂得去模拟一下第一次排序的过程吧，
第四行：@#￥%……&*
我知道大家肯定看晕了，我们先来回顾一下这几个数组的定义
sa[i]：排名为$i$的后缀的位置 rak[i]：从第$i$个位置开始的后缀的排名 tp[i]：基数排序的第二关键字，意义与sa一样
此时rak数组和tp数组都已经是排好序的，
‘所以我们此时做的就是拿这两个数组来更新sa数组
倒着循环的目的是让靠前的后缀先出现
后记
本蒟蒻也是第一次看这么难的东西。
第一次见这种东西应该是去年夏天吧，那时我记得自己在机房里瞅着这几行代码看了一晚上也没看出啥来。
现在再来看也是死磕了一天多才看懂。
不过我还是比较好奇。
这种东西是谁发明的啊啊啊啊啊脑洞也太大了吧啊啊啊啊啊啊
哦对了，后缀数组还有一个非常有用的数组叫做Height，这个数组更神奇，，有空再讲吧。