P3809 【模板】后缀排序

后缀数组sa[i]就表示排名为i的后缀的起始位置

x[i]是第i个元素的第一关键字

y[i]表示第二关键字排名为i的数，在第一关键字中的位置

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define N 1000005

#define rint register int

int n,m,c[N],sa[N],x[N],y[N]; char s[N];

void get_sa(){

    for(rint i=;i<=n;++i) ++c[x[i]=s[i]];

    for(rint i=;i<=m;++i) c[i]+=c[i-];

    for(rint i=n;i>=;--i) sa[c[x[i]]--]=i;

    for(rint k=;k<=n;k<<=){

        rint u=;

        for(rint i=n-k+;i<=n;++i) y[++u]=i;//逆序也没关系，因为都是没有

        for(rint i=;i<=n;++i) if(sa[i]>k) y[++u]=sa[i]-k;

        for(rint i=;i<=m;++i) c[i]=;

        for(rint i=;i<=n;++i) ++c[x[i]];

        for(rint i=;i<=m;++i) c[i]+=c[i-];

        for(rint i=n;i>=;--i) sa[c[x[y[i]]]--]=y[i],y[i]=;//按第二关键字排序

        swap(x,y); x[sa[]]=; u=;

        for(rint i=;i<=n;++i)

            x[sa[i]]=(y[sa[i]]==y[sa[i-]]&&y[sa[i]+k]==y[sa[i-]+k])?u:++u;

        if(u==n){break;} m=u;

    }

}

int main(){

    scanf("%s",s+); n=strlen(s+),m=;

    get_sa();

    for(rint i=;i<=n;++i) printf("%d ",sa[i]);

    return ;

}

sa求最长公共前缀

void get_height() //求最长公共前缀

{

    for(rint i=;i<=n;i++) rk[sa[i]]=i;

    rint k=;

    for(rint i=;i<=n;i++)

    {

        if(rk[i]==) continue;

        if(k) --k;

        rint j=sa[rk[i]-];

        while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) ++k;

        height[rk[i]]=k;

    }

}

秒客网

P3809 【模板】后缀排序

相关文章