Suffix Array

未分类

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll MAXN=1e6+51;
ll length,sigmaSize;
ll sa[MAXN],rk[MAXN],barrel[MAXN],s[MAXN];
char str[MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline void radixSort()
{
    for(register int i=0;i<=sigmaSize;i++)
    {
        barrel[i]=0;
    }
    for(register int i=1;i<=length;i++)
    {
        barrel[rk[i]]++;
    }
    for(register int i=1;i<=sigmaSize;i++)
    {
        barrel[i]+=barrel[i-1];
    }
    for(register int i=length;i;i--)
    {
        sa[barrel[rk[s[i]]]--]=s[i];
    }
}
inline void suffixArray()
{
    for(register int i=1;i<=length;i++)
    {
        rk[i]=str[i]-'0'+1,s[i]=i;
    }
    radixSort();
    for(register int gap=1,p=0;p<length;sigmaSize=p,gap<<=1)
    {
        p=0;
        for(register int i=1;i<=gap;i++)
        {
            s[++p]=length-gap+i;
        }
        for(register int i=1;i<=length;i++)
        {
            if(sa[i]>gap)
            {
                s[++p]=sa[i]-gap;
            }
        }
        radixSort();
        swap(s,rk);
        rk[sa[1]]=p=1;
        for(register int i=2;i<=length;i++)
        {
            rk[sa[i]]=s[sa[i-1]]==s[sa[i]]&&s[sa[i-1]+gap]==s[sa[i]+gap]?p:++p;
        }
    }
}
int main()
{
    scanf("%s",str+1);
    sigmaSize=128,length=strlen(str+1);
    suffixArray();
    for(register int i=1;i<=length;i++)
    {
        printf("%d ",sa[i]);
    }
}