2018-team4-modules-后缀数组

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
int wa[maxn],wb[maxn],ws[maxn];
int rank[maxn],height[maxn],sa[maxn];
bool cmp(int *r,int i,int j,int k){
    return r[i] == r[j] && r[i+k] == r[j+k];
}
void da(int *r,int n,int m){
    int i,j,p,*x = wa,*y = wb;
    for(i=0;i<m;++i) ws[i] = 0;
    for(i=0;i<n;++i) ws[x[i] = r[i]]++;
    for(i=1;i<m;++i) ws[i] += ws[i-1];
    for(i=n-1;i>=0;--i) sa[--ws[x[i]]] = i;
    for(j=1,p=1;p<n;j<<=1,m=p){
        for(p=0,i=n-j;i<n;++i) y[p++] = i;
        for(i=0;i<n;++i) if(sa[i] >= j) y[p++] = sa[i] - j;
        for(i=0;i<m;++i) ws[i] = 0;
        for(i=0;i<n;++i) ws[x[y[i]]]++;
        for(i=1;i<m;++i) ws[i] += ws[i-1];
        for(i=n-1;i>=0;--i) sa[--ws[x[y[i]]]] = y[i];
        for(swap(x,y),p=1,i=1,x[sa[0]] = 0;i<n;++i)
        x[sa[i]] = cmp(y,sa[i-1],sa[i],j) ? p-1 : p++;
    }
}
void get_h(int *r,int n){
    int i,j,k=0;for(i=1;i<=n;++i) rank[sa[i]] = i;
    for(i=0;i<n;height[rank[i++]] = k)
    for(k ? --k : 0,j = sa[rank[i]-1];r[i+k] == r[j+k];++k);
}
loger[maxn],minn[maxn][22],n;
inline void pre(){
    loger[1] = 0;
    for(int i=2;i<=n;++i){
        loger[i] = loger[i-1];
        if( (1 << loger[i]+1) == i) ++loger[i];
    }
    for(int i=n;i>=1;--i){
        minn[i][0] = height[i];
        for(int j=1;i+(1<<j)-1<=n;++j){
            minn[i][j] = min(minn[i][j-1],minn[i+(1<<j-1)][j-1]);
        }
    }
}
int lcp(int x,int y){
    if(x+1 > y) swap(x,y);++x;
    int k = loger[y-x+1];
    return min(minn[x][k],minn[y-(1<<k)+1][k]);
}
}}}

int wa[maxn],wb[maxn],ws[maxn];
int rank[maxn],height[maxn],sa[maxn];
bool cmp(int *r,int i,int j,int k){
    return r[i] == r[j] && r[i+k] == r[j+k];
}
void da(int *r,int n,int m){
    int i,j,p,*x = wa,*y = wb;
    for(i=0;i<m;++i) ws[i] = 0;
    for(i=0;i<n;++i) ws[x[i] = r[i]]++;
    for(i=1;i<m;++i) ws[i] += ws[i-1];
    for(i=n-1;i>=0;--i) sa[--ws[x[i]]] = i;
    for(j=1,p=1;p<n;j<<=1,m=p){
        for(p=0,i=n-j;i<n;++i) y[p++] = i;
        for(i=0;i<n;++i) if(sa[i] >= j) y[p++] = sa[i] - j;
        for(i=0;i<m;++i) ws[i] = 0;
        for(i=0;i<n;++i) ws[x[y[i]]]++;
        for(i=1;i<m;++i) ws[i] += ws[i-1];
        for(i=n-1;i>=0;--i) sa[--ws[x[y[i]]]] = y[i];
        for(swap(x,y),p=1,i=1,x[sa[0]] = 0;i<n;++i)
        x[sa[i]] = cmp(y,sa[i-1],sa[i],j) ? p-1 : p++;
    }
}
void get_h(int *r,int n){
    int i,j,k=0;for(i=1;i<=n;++i) rank[sa[i]] = i;
    for(i=0;i<n;height[rank[i++]] = k)
    for(k ? --k : 0,j = sa[rank[i]-1];r[i+k] == r[j+k];++k);
}
loger[maxn],minn[maxn][22],n;
inline void pre(){
    loger[1] = 0;
    for(int i=2;i<=n;++i){
        loger[i] = loger[i-1];
        if( (1 << loger[i]+1) == i) ++loger[i];
    }
    for(int i=n;i>=1;--i){
        minn[i][0] = height[i];
        for(int j=1;i+(1<<j)-1<=n;++j){
            minn[i][j] = min(minn[i][j-1],minn[i+(1<<j-1)][j-1]);
        }
    }
}
int lcp(int x,int y){
    if(x+1 > y) swap(x,y);++x;
    int k = loger[y-x+1];
    return min(minn[x][k],minn[y-(1<<k)+1][k]);
}