$O(nlogn)$版

要注意:
计数排序后面一定要逆序加回去，这样才能保证原来的顺序不被破坏

int sa[N],q1[N],q2[N],*rank=q1,*temp=q2;
//sa[i] suffix array 后缀数组 第i名的起始位置
//rank[i] 第i个起始位置的rank 
char s[N];
int num[N];

int n,i;
void get_sa()
{
    int m=255;
    for (i=1;i<=n;++i) ++num[s[i]];
    for (i=1;i<=m;++i) num[i]+=num[i-1];
    for (i=n;i;--i) sa[num[s[i]]--]=i;
    int last,now;
    m=rank[last=sa[1]]=1;
    for (i=2;i<=n;++i) 
    {
        now=sa[i];
        if (s[now]!=s[last]) ++m;
        rank[last=now]=m;
    }

    for (int l=1;m<n;l<<=1)//rank[i],rank[i+l]作关键字
    {
        //先以rank[i+l]作关键字排序 
        int top=0;
        //i>n-l的 i+l已经超出 直接放进来 
        for (i=n-l+1;i<=n;++i) temp[++top]=i;
        //i<=n-l的 可以利用上一次的sa
        for (i=1;i<=n;++i)
        if (sa[i]>l) temp[++top]=sa[i]-l;

        //在temp的基础上 以rank[i]为关键字 计数排序 
        memset(num,0,m+1<<2);
        for (i=1;i<=n;++i) ++num[rank[i]];
        for (i=2;i<=m;++i) num[i]+=num[i-1];
        for (i=n;i;--i) sa[num[rank[temp[i]]]--]=temp[i];

        std::swap(rank,temp);//temp存储原来的rank,来比较是否一样
        m=rank[last=sa[1]]=1;
        for (i=2;i<=n;++i)
        {
            now=sa[i];
            if (!(temp[now]==temp[last]&&temp[now+l]==temp[last+l])) ++m;
            rank[last=now]=m; 
        }
    } 
}