2013-team4/code/suffix-array

从 Trac 迁移的文章

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

原文章内容如下：

{{{
基数排序的倍增算法, 时间复杂度 O(nlogn)
用法：
build(str, len, sigma);
len 为字符串的普通长度，不包括最后的'\0'，其中每个字符的范围是 [0, sigma)
结束后 sa[], rank[], height[] 均得到计算，排序后第一个串不是空串，数组长度均为 len
下标均从 0 开始，height[i] 为 sa[i] 与 sa[i-1] 的 LCP 长度，height[0] 无意义
}}}
{{{
const int N = 100000;
struct SA{
    int tmp[2][N], c[N];
    int n, sa[N], *rank, height[N];
    const char *s;

    void getHeight(){
        for(int k = 0, i = 0; i < n; i++){
            if(rank[i] == 0) continue;
            if(k > 0) k--;
            int j = sa[rank[i] - 1];
            while(s[i + k] == s[j + k]) k++;
            height[rank[i]] = k;
        }
    }
    void build(const char *s, int n, int m){
        this->n = n; this->s = s;
        rank = tmp[0];
        memset(c, 0, sizeof(int) * m);
        for(int i = 0; i < n; i++) c[rank[i] = s[i]]++;
        for(int i = 1; i < m; i++) c[i] += c[i - 1];
        for(int i = 0; i < n; i++) sa[--c[rank[i]]] = i; 
        for(int *t = tmp[1], k = 1; k <= n; k <<= 1){
            int p = 0;
            for(int i = n - k; i < n; i++) t[p++] = i;
            for(int i = 0; i < n; i++) if(sa[i] >= k) t[p++] = sa[i] - k;
            //
            memset(c, 0, sizeof(int) * m);
            for(int i = 0; i < n; i++) c[rank[t[i]]]++;
            for(int i = 1; i < m; i++) c[i] += c[i - 1];
            for(int i = n - 1; i >= 0; i--) sa[--c[rank[t[i]]]] = t[i];
            //
            swap(rank, t);
            p = 1; rank[sa[0]] = 0;
            for(int i = 1; i < n; i++){
                int I = sa[i], J = sa[i - 1]; 
                int t1 = (J + k < n ? t[J + k] : -1), t2 = (I + k < n ? t[I + k] : -1);
                rank[sa[i]] = (t[J] == t[I] && t1 == t2 ? p - 1 : p++);
            }
            if(p >= n) break;
            m = p;
        }
        getHeight();
    }
};
}}}

基数排序的倍增算法, 时间复杂度 O(nlogn)
用法：
build(str, len, sigma);
len 为字符串的普通长度，不包括最后的'\0'，其中每个字符的范围是 [0, sigma)
结束后 sa[], rank[], height[] 均得到计算，排序后第一个串不是空串，数组长度均为 len
下标均从 0 开始，height[i] 为 sa[i] 与 sa[i-1] 的 LCP 长度，height[0] 无意义

const int N = 100000;
struct SA{
    int tmp[2][N], c[N];
    int n, sa[N], *rank, height[N];
    const char *s;
    void getHeight(){
        for(int k = 0, i = 0; i < n; i++){
            if(rank[i] == 0) continue;
            if(k > 0) k--;
            int j = sa[rank[i] - 1];
            while(s[i + k] == s[j + k]) k++;
            height[rank[i]] = k;
        }
    }
    void build(const char *s, int n, int m){
        this->n = n; this->s = s;
        rank = tmp[0];
        memset(c, 0, sizeof(int) * m);
        for(int i = 0; i < n; i++) c[rank[i] = s[i]]++;
        for(int i = 1; i < m; i++) c[i] += c[i - 1];
        for(int i = 0; i < n; i++) sa[--c[rank[i]]] = i; 
        for(int *t = tmp[1], k = 1; k <= n; k <<= 1){
            int p = 0;
            for(int i = n - k; i < n; i++) t[p++] = i;
            for(int i = 0; i < n; i++) if(sa[i] >= k) t[p++] = sa[i] - k;
            //
            memset(c, 0, sizeof(int) * m);
            for(int i = 0; i < n; i++) c[rank[t[i]]]++;
            for(int i = 1; i < m; i++) c[i] += c[i - 1];
            for(int i = n - 1; i >= 0; i--) sa[--c[rank[t[i]]]] = t[i];
            //
            swap(rank, t);
            p = 1; rank[sa[0]] = 0;
            for(int i = 1; i < n; i++){
                int I = sa[i], J = sa[i - 1]; 
                int t1 = (J + k < n ? t[J + k] : -1), t2 = (I + k < n ? t[I + k] : -1);
                rank[sa[i]] = (t[J] == t[I] && t1 == t2 ? p - 1 : p++);
            }
            if(p >= n) break;
            m = p;
        }
        getHeight();
    }
};