对于后缀有关的东西，本人一无所知。
如果你点击进来这博客，那请你谨慎阅读。
本菜鸡在开开心心刷沈大佬给我拉的铜牌题专题的时候，突然遇到了一到后缀自动机的题，不过，我完全不会。上网搜索资料的时候，我看到了后缀数组，后缀自动机，后缀树这几个东西，我也不知道他们是干什么的，也不知道他们的难度如何，于是就找了一个看起来最简单的来学一下。
此博客会基于挑战，谈一些自己现在的理解。由于是本菜鸡的初步理解，再次重申，请谨慎阅读！！
所谓后缀数组，就是先拿到某个数组的所有后缀，给他们加上一个标号id，再将他们排个序，最后得到id的序列就是后缀数组。
请大家看一下我的暴力代码：
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string s;
const int maxn = 10086;
struct node
{
string ss;
int id;
}sa[maxn];
bool cmp(node x,node y)
{
return x.ss<y.ss;
}
int main()
{
ios::sync_with_stdio(false);
cin>>s;
int l=s.length();
for(int i=l;i>=0;i--){
sa[i].ss=sa[i+1].ss;
sa[i].ss.insert(sa[i].ss.begin(),s[i]);//得到后缀
sa[i].id=i;//打上标号
}
sort(sa,sa+l+1,cmp);//根据后缀排序
//最后，id顺序就是后缀数组的内容
for(int i=0;i<=l;i++){
cout<<sa[i].id<<" ";
}
cout<<endl;
return 0;
}
这样的暴力时间复杂度取决于string的插入操作，其他的地方就只有一个sort有nlog(n)的复杂度，本菜鸡并不知道string的复杂度是多少，不过据我分析，应该是n2的。
就此而言，整个算法的时间复杂度就应该是n2的。
所以，挑战上给我们介绍了一种nlog2n的算法。
整个算法的过程挑战已经说得非常清楚了，在P378.所以我会再次讲解一下他的代码。
一下代码是一个一个字直接打出来，但愿我没有抄错，不过测了一点数据，和暴力的输出是一样的。
//未完待续
原文：https://www.cnblogs.com/ZGQblogs/p/9746886.html