SA

推荐blog：这里       还有这里

SA确实非常的妙

就是它先用计数排序将每一个后缀的第一个字母排好序，接着将排序的范围扩大到2

因为处理好了第一个字母，那么在这个字母之前加一个字母，这时只要再用计数排好第一个字母，（见计数排序的性质）

那么所有后缀的前两位都是整齐的了，

又因为这时已经有了一个顺序，那么可以将这前两个排好序的字符绑起来，给他们一个标号，再用这个标号，给所有后缀的前4位进行排序（字母个数不足的排除在外）

以此类推，倍增到最后，所有后缀便都是有序的了

还有那些被排除出来的，因为之前它们首字母标签（也就是第一关键字）会在上一次排序中被赋值，按照首字母的关键字进行排序就可以保证一定有序了

详细见代码

#include<bits/stdc++.h>
using namespace std;
int c[1000006],y[1000006],x[1000006],sa[1000006];
string s;
int m,n,num;
void get_SA(){
    int i,j,k,p;
    for(i=0;i<n;i++)c[x[i+1]=s[i]]++;
    for(i=2;i<=m;i++)c[i]+=c[i-1];
    //for(i='a';i<='z';i++)printf("%d ",c[i]);
    //printf("
");
    for(i=n;i>=1;i--)sa[c[x[i]]--]=i;
    
    for(k=1;k<=n;k<<=1){
        p=0;
        for(i=n-k+1;i<=n;i++)y[++p]=i;
        for(i=1;i<=n;i++)
            if(sa[i]>k)y[++p]=sa[i]-k;
        //for(i=1;i<=n;i++)printf("%d ",y[i]);
        //    printf("
");
        for(i=1;i<=m;i++)c[i]=0;
        for(i=1;i<=p;i++)
            c[x[i]]++;
        for(i=2;i<=m;i++)
            c[i]+=c[i-1];
        for(i=n;i>=1;i--)
            sa[c[x[y[i]]]--]=y[i];
        
        swap(x,y);
        num=1;
        x[sa[1]]=1;
        for(i=2;i<=p;i++){
            if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])x[sa[i]]=num;
            else x[sa[i]]=++num;
        }
        if(num==n)break;
        m=num;
    }
    for(i=1;i<=n;i++)printf("%d ",sa[i]);
}
int main(){
    cin>>s;
    n=s.length();
    m=122;
    get_SA();
    return 0;
}