后缀数组

说明

本算法的实现使用:DA算法

将字符串s分割为len个后缀串,然后将这len个字符串按照字典序排放,每一个后缀串可以用第一个字符在原串中的位置表示,用sa[]数组存储字典序从小到大的后缀串的首字符下标。rk[]数组表示对于当前串,在sa数组中的下标位置。ht[i]数组表示sa[i]和sa[i-1]表示的两个后缀串的公共前缀长度。

用法

  1. getSa(s, len+1, 'z'+1); 对于从0开始的字符串s,长度为len,最大值为'z'
  2. getHet(s, len);当获取过Sa数组后 对于从0开始的字符串,长度为len

Tips

  • 分清下标,见主函数

模版

/*
 2016.7.31
 rk的有效信息从0到n-1
 sa,ht的有效信息从1到n
 在传参的时候要多传一位*/
const int maxn=100000+5;
int rk[maxn], sa[maxn], ht[maxn], wa[maxn], wb[maxn], wx[maxn], wv[maxn];

bool isq(int *r, int a, int b, int len) {
    return r[a] == r[b] && r[a + len] == r[b + len];
}

bool isEqual(int *r, int a, int b, int len) {
    return r[a] == r[b] && r[a + len] == r[b + len];
}
// r数组有效信息为0~n-1,m为(数组中最大值的上界+1)
void getSa(char r[], int n, int m) {
    int i, j, p, *t, *x = wa, *y = wb;
    for (i = 0; i < m; ++i)
        wx[i] = 0;
    for (i = 0; i < n; ++i)
        ++wx[x[i] = r[i]];
    for (i = 1; i < m; ++i)
        wx[i] += wx[i - 1];
    for (i = n - 1; i >= 0; --i)
        sa[--wx[x[i]]] = i;
    for (j = 1, p = 0; p < n; j <<= 1, m = p) {
        for (p = 0, i = n - j; i < n; ++i)
            y[p++] = i;
        for (i = 0; i < n; ++i)
            sa[i] >= j ? y[p++] = sa[i] - j : 0;
        for (i = 0; i < m; ++i)
            wx[i] = 0;
        for (i = 0; i < n; ++i)
            ++wx[wv[i] = x[y[i]]];
        for (i = 1; i < m; ++i)
            wx[i] += wx[i - 1];
        for (i = n - 1; i >= 0; --i)
            sa[--wx[wv[i]]] = y[i];
        p = 1, t = x, x = y, y = t;
        x[sa[0]] = 0;
        for (i = 1; i < n; ++i)
            x[sa[i]] = isEqual(y, sa[i], sa[i - 1], j) ? p - 1 : p++;
    }
}

void getHet(char r[], int n) {
    int i, j, k = 0;
    for (i = 1; i <= n; ++i)
        rk[sa[i]] = i;
    for (i = 0; i < n; ht[rk[i++]] = k) {
        k = k > 0 ? k - 1 : 0;
        j = sa[rk[i] - 1];
        while (r[i + k] == r[j + k])
            ++k;
    }
}
int main(){

    char s[maxn]="banana";
    int len =strlen(s);

    //用法
    getSa(s, len+1, 'z'+1); //对于从0开始的字符串s,长度为len,最大值为'z'
    getHet(s, len); //当获取过Sa数组后 对于从0开始的字符串,长度为len

    //备注:sa[]和rk符合逆运算 即同时满足sa[i]=j rk[j]=i
    for (int i=1; i<=len; i++) {
        printf("%d%c",sa[i]," \n"[i==len]);
    }// 输出sa数组 下标从 1~len 值为:5 3 1 0 4 2

    for (int i=0; i<len; i++) {
        printf("%d%c",rk[i]," \n"[i==len-1]);
    }// 输出rk数组 下标从 0~len-1 值为:4 3 6 2 5 1

    for (int i=1; i<=len; i++) {
        printf("%d%c",ht[i]," \n"[i==len]);
    }// 输出ht数组 下标从 1~len 值为:0 1 3 0 0 2
}

results matching ""

    No results matching ""