upd|´・ω・)ノ:注意如果使用封装的求SA,要每次都清c数组(memset,不然会残余上次的qwq 3.8

upd:排名越近的两个公共前缀必然越长

后缀数组:

suff(i):以s的第i个字符为第一个元素的后缀

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

而它的映射数组rk[i]就表示起始位置的下标为i的后缀的排名

LCP(i,j)为suff(sa[i])与suff(sa[j])的最长公共前缀

  1. $LCP(i,j)=LCP(j,i);$
  2. $LCP(i,i)=len(sa[i])=n-sa[i]+1$

性质:

$LCP(i,k)=min(LCP(i,j),LCP(j,k)) 对于任意1<=i<=j<=k<=n​$

$LCP(i,k)=min(LCP(j,j-1)) 对于任意1<i<j<=k<=n$

设$pub(i)=lcp(i,i-1)$,$h(i)=pub(rk[i])=suff(i)和suff(sa[rk[i]-1])的最长公共前缀$

结论:$h(i)>=h(i-1)-1$

#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
char s[maxn];
int t1[maxn],t2[maxn],c[maxn],sa[maxn],a[maxn],pub[maxn];
void solve(int n,int m){
        memset(c,0,sizeof(c));
    int *x=t1,*y=t2;
    for(int i=1;i<=n;i++) c[x[i]=a[i]]++;
    for(int i=1;i<=m;i++) c[i]+=c[i-1];
    for(int i=n;i>=1;i--) sa[c[x[i]]--]=i;
    for(int k=1;k<=n;k<<=1){
        int num=0;
        for(int i=n-k+1;i<=n;i++) y[++num]=i;
        for(int i=1;i<=n;i++) if(sa[i]>k) y[++num]=sa[i]-k;
        for(int i=1;i<=m;i++) c[i]=0;
        for(int i=1;i<=n;i++) c[x[i]]++;
        for(int i=1;i<=m;i++) c[i]+=c[i-1];
        for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i],y[i]=0;//y[i]表示y排名为i的下标 
        swap(x,y);
        num=1;x[sa[1]]=1;
        for(int i=2;i<=n;i++){
            x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
        }
        if(num==n) break;
        m=num;
    }
    for(int i=1;i<=n;i++) printf("%d ",sa[i]);
}
void lcp(){
    int k=0;
    for(int i=1;i<=n;i++) rk[sa[i]]=i;
    for(int i=1;i<=n;i++){
        if(rk[i]==1) continue;
        if(k) k--;
        int j=sa[rk[i]-1];
        while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k]) k++;
        pub[rk[i]]=k;
    }
}
int n;
void init(){
    scanf("%s",s);
    int len=strlen(s);
    n=0;
    for(int i=0;i<len;i++) a[++n]=s[i];
    solve(n,122);
    lcp(); 
}
int main(){
    init();
    
    return 0;
}
Last modification:April 5th, 2019 at 10:27 am