后缀数组 学习笔记

发表于 | 分类于 | | + s

模板及讲解

性质

1、字符串中的子串可以表示为后缀的前缀，即后缀的LCP。

模板、代码

解决字符串的有力工具。
直接上代码，注释讲解(此题为uoj #35)
(注意：下标都是从0开始)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define FN2 "uoj35" 
using namespace std;

const int MAXN = 1000000 + 5;

char ch[MAXN];
int a[MAXN], n, m;
//ch为输入字符串，a为处理后的整数原串 
int SA[MAXN], rk[MAXN], tp[MAXN], tax[MAXN], height[MAXN];
/*
    SA[i]: 排名第i的后缀的位置(下标是后缀排名)
     rk[i]: 第i个后缀的排名
    tp[i]: 排名为i的第二关键字的第一关键字的位置 (下标是第二关键字排名)
    tax[i]:基数排序的桶
    height[i]: 排名为i, i-1后缀的最长公共前缀 
*/
bool cmp(int *f, int i, int k) {return f[SA[i-1]]==f[SA[i]]&&f[SA[i-1]+k]==f[SA[i]+k];} //要判断两个字符串是否完全相等 
void build() {//构造后缀数组 
    int i, p;
    for (int i=0;i<m;i++) tax[i] = 0;
    for (int i=0;i<n;i++) tax[rk[i]=a[i]]++;
    for (int i=0;i<m;i++) tax[i] += tax[i-1];
    for (int i=n-1;i>=0;i--) SA[--tax[rk[i]]] = i;//基数排序排第一轮

    for (int k=1;k<=n;k*=2) {
        p = 0;
        for (int i=n-k;i<n;i++) tp[p++] = i;//(n-k)~(n-1)无第二关键字，所以排序应该排在前面
        for (int i=0;i<n;i++) if (SA[i]>=k) tp[p++] = SA[i] - k;
        //只有SA[i]>=k的SA[i]才是第二关键字的位置 
        //从图中可以看出第一关键字和第二关键字的位置相差k，故SA[i] - k 
        for (int i=0;i<m;i++) tax[i] = 0;
        for (int i=0;i<n;i++) tax[rk[tp[i]]]++;//x[tp[i]]相等于排名第i的第二关键字的第一关键字的排名 
        for (int i=1;i<m;i++) tax[i] += tax[i-1];
        for (int i=n-1;i>=0;i--) SA[--tax[rk[tp[i]]]] = tp[i];//保证了第一关键字的顺序再排第二关键字 
        //基数排序第一关键字(rank[i]的数值)和第二关键字(tp[i]的下标) 
        swap(rk, tp);//此时tp没用，暂存上一轮rank的值
        p = 0, rk[SA[0]] = 0;//sa[0]一定是添加的字符0, 排名一定是0
        for (int i=1;i<n;i++) rk[SA[i]] = cmp(tp, i, k) ? p : ++p;
        //算排名第i的数的rank，按sa顺序能够保证rank的正确性，但是要cmp判断与上一个字符串相等的情况 
        if (++p>=n) break;//剪枝，已经没有重复元素 
        m = p; 
    }
}
void getH() {//算height 
    int i, j, k = 0;//k是比i-1前一名的后缀
    for (int i=0;i<n;i++) {//H[0], H[1], H[2] ...的顺序计算 
        if (k) k--;//从k-1开始比较 ,运用结论H[i]>=H[i-1]-1, 最长公共前缀的长度至少是k-1(k = H[i-1])
        j = SA[rk[i]-1]; //前一名的后缀位置 
        while(ch[i+k] == ch[j+k]) k++; //往后比较 
        height[rk[i]] = k;  //更新答案 
    }
}
void init() {
    int i;
    n = strlen(ch) + 1, m = 128;
    for (int i=0;i<n-1;i++) a[i] = ch[i];//处理原字符串 
    a[n - 1] = 0;//补末尾的0 
}
void solve() {
    int i;
    build(); 
    getH();
    for (int i=1;i<n;i++) printf("%d ", SA[i]+1);//输出范围1~n-1 
    printf("\n");
    for (int i=2;i<n;i++) printf("%d ", height[i]);
}
int main() {
    scanf("%s", ch), init(), solve();
    return 0;
}

从1开始的SA (不用补0)：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define FN2 "uoj35" 
using namespace std;

const int MAXN = 1000000 + 5;

char ch[MAXN];
int a[MAXN], n, m;
//ch为输入字符串，a为处理后的整数原串 
int SA[MAXN], rk[MAXN], tp[MAXN], tax[MAXN], height[MAXN];
/*
    SA[i]: 排名第i的后缀的位置(下标是后缀排名)
     rk[i]: 第i个后缀的排名
    tp[i]: 排名为i的第二关键字的第一关键字的位置 (下标是第二关键字排名)
    tax[i]:基数排序的桶
    height[i]: 排名为i, i-1后缀的最长公共前缀 
*/
void build() {//构造后缀数组 
    for (int i = 1; i <= m; ++i) tax[i] = 0;
    for (int i = 1; i <= n; ++i) tax[rk[i] = a[i]]++;
    for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
    for (int i = n; i >= 1; --i) SA[tax[rk[i]]--] = i;//基数排序排第一轮

    for (int k = 1; k <= n; k *= 2) {
        int p = 0;
        for (int i = n - k + 1; i <= n; i++) tp[++p] = i;//(n-k)~(n-1)无第二关键字，所以排序应该排在前面
        for (int i = 1; i <= n; i++) if (SA[i] > k) tp[++p] = SA[i] - k;
        //只有SA[i]>=k的SA[i]才是第二关键字的位置 
        //从图中可以看出第一关键字和第二关键字的位置相差k，故SA[i] - k 
        for (int i = 1; i <= m; ++i) tax[i] = 0;
        for (int i = 1; i <= n; ++i) tax[rk[tp[i]]]++;//x[tp[i]]相等于排名第i的第二关键字的第一关键字的排名 
        for (int i = 1; i <= m; ++i) tax[i] += tax[i - 1];
        for (int i = n; i >= 1; --i) SA[tax[rk[tp[i]]]--] = tp[i];//保证了第一关键字的顺序再排第二关键字 
        //基数排序第一关键字(rank[i]的数值)和第二关键字(tp[i]的下标) 
        swap(rk, tp);//此时tp没用，暂存上一轮rank的值
        p = 1, rk[SA[1]] = 1;
        for (int i = 2; i <= n; ++i) 
            rk[SA[i]] = (tp[SA[i]] == tp[SA[i - 1]] && tp[SA[i] + k] == tp[SA[i - 1] + k]) ? p : ++p;
        //算排名第i的数的rank，按sa顺序能够保证rank的正确性，但是要cmp判断与上一个字符串相等的情况 
        if (p >= n) break;//剪枝，已经没有重复元素 
        m = p; 
    }
}
void getH() {//算height 
    int k = 0;//k是比i-1前一名的后缀
    for (int i = 1; i <= n; ++i) {//H[0], H[1], H[2] ...的顺序计算 
        if (k) k--;//从k-1开始比较 ,运用结论H[i]>=H[i-1]-1, 最长公共前缀的长度至少是k-1(k = H[i-1])
        int j = SA[rk[i] - 1]; //前一名的后缀位置 
        while(ch[i + k] == ch[j + k]) k++; //往后比较 
        height[rk[i]] = k;  //更新答案 
    }
}
void solve() {
    n = strlen(ch + 1), m = 256;
    for (int i = 1; i <= n; ++i) a[i] = ch[i];//处理原字符串 
    build(); 
    getH();
    for (int i = 1; i <= n; ++i) printf("%d ", SA[i]); 
    printf("\n");
    for (int i = 2; i <= n; ++i) printf("%d ", height[i]);
}
int main() {
    scanf("%s", ch + 1), solve();
    return 0;
}

写时注意：
1、不要将字符对应到0
2、不同字符串之间一定要用不同字符连接
3、用不同字符串连接字符串后注意空间开大

常见题型

LCP相关

1、LCP入手：Bzoj 4650
2、子串=后缀LCP：Bzoj 4650, Bzoj 4199, Bzoj 4566, Spoj 694
3、所有串的LCP(单调栈 / 并查集)：Bzoj 4199, Bzoj 3238, Bzoj 4566

其他

1、二分后SA(Height分组)：Hdu 2328
2、ST表+二分查找 (仅用于求出询问的区间)：Bzoj 2754，Bzoj 3172
3、多次求后缀数组：Bzoj 4698, Hdu 2328

与Height无关

1、SA的单调性：Bzoj 2754
2、后缀数组的后缀排序运用：Bzoj 1031

------ 本文结束 ------