# 后缀数组模板

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1000001;
char s[N];
int rnk[N],sa[N],rnk1[N],cnt[N],t[N],len,m,h[N];
//rnk->第一关键字  sa->后缀数组  cnt->桶  t->第二关键字 rnk1->排名 h->最长公共前缀长度 
void sort()
{
	for(int i=0;i<=m;i++)
	    cnt[i]=0;
	for(int i=1;i<=len;i++)
	    cnt[rnk1[t[i]]]++;
	for(int i=1;i<=m;i++)
	    cnt[i]+=cnt[i-1];
	for(int i=len;i>=1;i--)
	    sa[cnt[rnk1[t[i]]]--]=t[i];
	return;
}
void get_sa()
{
	for(int i=1;i<=len;i++) //初始化 
	    rnk1[i]=s[i],t[i]=i;
	sort();
	for(int l=1;l<=len;l*=2)
	{
	    int id=0;
	    for(int i=len-l+1;i<=len;i++)
	        t[++id]=i;
	    for(int i=1;i<=len;i++)
	        if(sa[i]>l)
	            t[++id]=sa[i]-l;
	    sort();
	    swap(t,rnk1);
	    rnk1[sa[1]]=1;
	    id=1;
	    for(int i=2;i<=len;i++)
	    {
	        if(t[sa[i]]==t[sa[i-1]] && t[sa[i]+l]==t[sa[i-1]+l])
	        	rnk1[sa[i]]=id;
	        else
	        	rnk1[sa[i]]=++id;
	    }
	    if(id==len)
	        break;
	    m=id;
	}
	return;
}
void get_h()
{
	int l=0;
	for(int i=1;i<=len;i++)
	{
		int j=sa[rnk1[i]-1];
		while(i+l<=len && j+l<=len && s[i+l]==s[j+l])
			l++;
		h[rnk1[i]]=l;
		if(l>0)
			l--;
	}
	return;
}
int main()
{
    scanf("%s",s+1);
    len=strlen(s+1);
    m=123;
    get_sa();
    for(int i=1;i<=len;i++)
    printf("%d ",sa[i]);
    return 0;
}

例题：后缀排序

有人可能问后缀数组都有了那么后缀自动机呢？这个问题很容易解释，那就是 —————————————————————————— 笔者不会。。。