字符串-后缀数组

Love The Way You Lie 2021-11-16 23:24 340阅读 0赞

倍增法，每次排2^j长度的段，转移就是双关键字排序就好啦！

求height可以利用height\[rank\[i\]\]>=height\[rank\[i-1\]\]-1的性质，当然证明考虑构造，并反证，假设在其中插入元素使性质不成立，推矛盾就可以了。

基本上是从网上抄来的模板啦，解释一下代码吧~

x在交换之前充当了rank的功能。

关于c的用处，来看计数排序的实现方法：

for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
        ++c[a[i]];
    }
    for(i=1;i<=m;i++)
        c[i]+=c[i-1];
    for(i=n;i;i--)
        p[c[a[i]]--]=i;
    for(i=1;i<=n;i++)
        printf("%d",a[p[i]]);

y是按后半部分排序后前半部分开头序号，即x\[y\[i\]+j\]是单调的。

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int N=1e6+6;
    
    char s[N];
    int t1[N],t2[N],c[N];
    int sa[N],rk[N],ht[N];
    
    void gtsa(int n,int m){
        int i,j,p=0,*x=t1,*y=t2;
        for(i=1;i<=n;i++)
            ++c[x[i]=s[i]];
        for(i=1;i<=m;i++)
            c[i]+=c[i-1];
        for(i=n;i;i--)
            sa[c[x[i]]--]=i;
        for(i=1;i<=m;i++)
            c[i]=0;
        for(j=1;j<=n&&p<n;j<<=1){
            p=0;
            for(i=n-j+1;i<=n;i++)
                y[++p]=i;
            for(i=1;i<=n;i++)
                if(sa[i]>j)
                    y[++p]=sa[i]-j;
            for(i=1;i<=n;i++)
                ++c[x[y[i]]];
            for(i=1;i<=m;i++)
                c[i]+=c[i-1];
            for(i=n;i;i--)
                sa[c[x[y[i]]]--]=y[i];
            for(i=1;i<=m;i++)
                c[i]=0;
            swap(x,y);
            p=1;
            x[sa[1]]=1;
            for(i=2;i<=n;i++)
                x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j])?p:++p;
            m=p;
        }
        for(i=1;i<=n;i++)
            rk[sa[i]]=i;
        p=0;
        for(i=1;i<=n;i++){
            j=sa[rk[i]-1];
            if(p)--p;
            while(s[i+p]==s[j+p])++p;
            ht[rk[i]]=p;
        }
    }
    
    int main()
    {
        scanf("%s",s+1);
        int l=strlen(s+1);
        gtsa(l,127);return 0;
    }

如果实在不能理解，可以先看一下这份冗长而低效的方法：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int N=3e5+5;
    
    char s[N];
    int sa[N],rk[N],ht[N];
    struct elm{
        int x,r1,r2;
        bool operator==(elm a)const{
            return r1==a.r1&&r2==a.r2;
        }
    }p[N],q[N];
    int sm[N];
    
    void gtsa(int n,int m){
        int i,j;
        for(i=1;i<=n;i++)
            p[i]=(elm){i,s[i],0};
        for(i=1;i<=m;i++)
            sm[i]=0;
        for(i=1;i<=n;i++)
            ++sm[p[i].r2];
        for(i=1;i<=m;i++)
            sm[i]+=sm[i-1];
        for(i=n;i;i--)
            q[sm[p[i].r2]--]=p[i];
        for(i=1;i<=n;i++)
            p[i]=q[i];
        for(i=1;i<=m;i++)
            sm[i]=0;
        for(i=1;i<=n;i++)
            ++sm[p[i].r1];
        for(i=1;i<=m;i++)
            sm[i]+=sm[i-1];
        for(i=n;i;i--)
            q[sm[p[i].r1]--]=p[i];
        for(i=1;i<=n;i++)
            p[i]=q[i];
        m=1;
        q[1].r1=m;
        for(i=2;i<=n;i++)
            q[i].r1=(p[i]==p[i-1]?m:++m);
        for(i=1;i<=n;i++)
            p[i]=q[i];
        for(j=1;j<=n&&m<n;j<<=1){
            for(i=1;i<=n;i++)
                sm[i]=0;
            for(i=1;i<=n;i++)
                ++sm[p[i].x];
            for(i=1;i<=n;i++)
                sm[i]+=sm[i-1];
            for(i=n;i;i--)
                q[sm[p[i].x]--]=p[i];
            for(i=1;i<=n;i++)
                p[i]=q[i];
            for(i=n-j+1;i<=n;i++)
                p[i].r2=0;
            for(i=1;i<=n-j;i++)
                p[i].r2=p[i+j].r1;
            for(i=1;i<=m;i++)
                sm[i]=0;
            for(i=1;i<=n;i++)
                ++sm[p[i].r2];
            for(i=1;i<=m;i++)
                sm[i]+=sm[i-1];
            for(i=n;i;i--)
                q[sm[p[i].r2]--]=p[i];
            for(i=1;i<=n;i++)
                p[i]=q[i];
            for(i=1;i<=m;i++)
                sm[i]=0;
            for(i=1;i<=n;i++)
                ++sm[p[i].r1];
            for(i=1;i<=m;i++)
                sm[i]+=sm[i-1];
            for(i=n;i;i--)
                q[sm[p[i].r1]--]=p[i];
            for(i=1;i<=n;i++)
                p[i]=q[i];
            m=1;
            q[1].r1=m;
            for(i=2;i<=n;i++)
                q[i].r1=(p[i]==p[i-1]?m:++m);
            for(i=1;i<=n;i++)
                p[i]=q[i];
        }
        for(i=1;i<=n;i++)
            sa[i]=p[i].x,
            rk[p[i].x]=i;
        for(i=1,j=0;i<=n;i++){
            if(j)--j;
            while(s[i+j]==s[sa[rk[i]-1]+j])
                ++j;
            ht[rk[i]]=j;
        }
    }
    
    int main()
    {
        scanf("%s",s+1);
        int l=strlen(s+1);
        gtsa(l,127);
        for(int i=1;i<=l;i++)
            printf("%d ",sa[i]);
        return 0;
    }

更高效的算法请右转后缀自动机……

转载于:https://www.cnblogs.com/l-ly-03/p/String-SuffixArray.html