1. 首页
  2. 算法模板

后缀数组

简介

给定一个 0-Based 字符串 Str,将它的所有后缀进行排序。
数组 sa[i] 中保存排名第 i 的后缀的在字符串的那个位置,数组 rank[i] 表示从位置 i 开始的子串的排名。
数组 height[i] 表示排名第 i 的字符串和排名第 i+1 的字符串的公共前缀长度。

代码

namespace SuffixArray{
    const int Maxn=1e5+50;
    int cnt[Maxn+5];

    inline void radix(int str[],int pos[],int sa[],int n,int m){
        memset(cnt,0,sizeof(cnt));
        for (int i=0;i<n;i++) cnt[str[pos[i]]]++;
        for (int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
        for (int i=n-1;i>=0;i--) sa[--cnt[str[pos[i]]]]=pos[i];
    }


    int rank[Maxn+5],a[Maxn+5],b[Maxn+5];
    inline void SA(int str[],int sa[],int n,int m){
        for (int i=0;i<n;i++) rank[i]=i;
        radix(str,rank,sa,n,m);
        rank[sa[0]]=0;
        for (int i=1;i<n;i++)
            rank[sa[i]] = rank[sa[i-1]] + (str[sa[i]]!=str[sa[i-1]]);

        for (int k=1;k<=n;k<<=1){
            for (int j=0;j<n;j++){
                a[j]=rank[j]+1;
                b[j]=(j+k>=n?0:rank[j+k]+1);
                sa[j]=j; 
            } 
            radix(b,sa,rank,n,n);
            radix(a,rank,sa,n,n);
            rank[sa[0]]=0;
            for (int i=1;i<n;i++)
                rank[sa[i]] = rank[sa[i-1]] + (a[sa[i]]!=a[sa[i-1]] || b[sa[i]]!=b[sa[i-1]]);
        }
    }


    inline void getHeight(int str[],int sa[],int rank[],int height[],int n){
        for (int i=0;i<n;i++) rank[sa[i]]=i;
        int k=0;
        height[0]=0;
        for (int i=0;i<n;i++){
            k=(k==0?0:k-1);
            if (rank[i]!=0)
                while(str[i+k]==str[sa[rank[i]-1]+k]) k++;
            height[rank[i]]=k; 
        }
    }
}
评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
0
上一篇:
:下一篇

发表评论

gravatar

沙发空缺中,还不快抢~