之前写的 $O(n \log^2 n)$ 过了。

但是 $O(n \log n)$ 怎么在最大数据跑了十几秒。

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
char s[maxn];
int n;
int rk[maxn<<1],sa[maxn<<1];
int oldrk[maxn<<1];
vector<int> bar1[maxn],bar2[maxn];
int main()
{
  //  freopen("P3809_8.in","r",stdin);
    freopen("out","w",stdout);
    scanf("%s",s+1);
    n=strlen(s+1);
    int maxrk=n;
    for(int i=1;i<=n;i++)
    {
        sa[i]=i,rk[i]=s[i];
        maxrk=max(maxrk,rk[i]);
    }
    for(int w=1;w<n;w<<=1)
    {
       for(int i=1;i<=n;i++)
       {
            bar1[rk[i+w]].emplace_back(i);
       }
        for(int i=0;i<=maxrk;i++)
        {
            for(int v:bar1[i])
            {
                bar2[rk[v]].emplace_back(v);

            }
        }
        int cnt=0;
        for(int i=1;i<=maxrk;i++)
        {
            for(int v:bar2[i])
            {
                sa[++cnt]=v;
            }
        }
        for(int i=0;i<=maxrk;i++)oldrk[i]=rk[i];
        //printf("cnt = %d\n",cnt);
     //   assert(cnt==n);
        for(int i=1,p=0;i<=n;i++)
        {
            if(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w])
            {
                rk[sa[i]]=p;
            }
            else rk[sa[i]]=++p;
        }
        for(int i=0;i<=maxrk;i++)
        {
            bar1[i].clear(),bar2[i].clear();
            bar1[i].shrink_to_fit(),bar2[i].shrink_to_fit();
        }
    }
    for(int i=1;i<=n;i++)printf("%d ",sa[i]);
    return 0;
}