后缀数组定义与实现

定义

后缀

从字符串某个位置i到字符串末尾的子串，定义s的第i个字符为第一个元素的后缀为suf(i)。

后缀数组

把s的每一个后缀按照字典序排序，后缀数组sa[i]表示排名为i的后缀的起始位置的下标。rk[i]数组代表起始位置为i的后缀的排名。

rk[]和sa[] 是一一对应关系，互为逆运算，可以相互推导

倍增

倍增法求后缀数组是从字符串的第一个字符开始比较，然后每次倍增比较长度，直到完成。每次都递增两倍，所以总步骤一共只有 \log_2 n 次，非常高效。

优化

如果字符串很长，包含10000个字符，那么在最后一步，每个数字都有10000位，无法存储与排序。

方法是在每步操作后就对组合数字进行排序，用序号产生一个新数字，再用新数字进行下一步排序。

基数排序即可。

height数组

大概是SA里最核心，最有用的部分。

height[i] 表示 suf(sa[i]) 与 suf[sa[i -1]] 的最长公共前缀(LCP)。

性质：height[i] \ge height[rk[i - 1]]-1 。

lcp求解：lcp(i, j) = \min_{k =rk[i]+1}^{rk[j]} height[k]​

代码

const int N = 1e6 + 7;
int sa[N], rk[N], c[N], x[N], y[N], height[N];
​
char s[N];
int n, m;
​
void get_sa() {
    for(int i = 1; i <= n; i ++) c[x[i] = s[i]] ++;
    for(int i = 2; i <= m; i ++) c[i] += c[i - 1];
    for(int i = n; i; i --) sa[c[x[i]] --] = i;
    for(int k = 1; k <= n; k *= 2) {
        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 = 2; i <= m; i ++) c[i] += c[i - 1];
        for(int i = n; i; i --) sa[c[x[y[i]]] --] = y[i], y[i] = 0;
        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;
    }
}
void get_height() {
    for(int i = 1; i <= n; i ++) rk[sa[i]] = i;
    int k = 0;
    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 ++;
        height[rk[i]] = k;
    }
}

题目

sa数组的应用

P4051 [JSOI2007] 字符加密

把原串拼一个在后面，求出sa数组后，如果这个位置在原串里，那输出对应结尾的字符。

int main() {
    cin >> s;
    n = s.size() * 2;
    s = ' ' + s + s;
    m = 300;
    get_sa();
    for(int i = 1; i <= n; i ++) {
        if(sa[i] <= n / 2) cout << s[sa[i] + n / 2 - 1];
    }
}

height数组的应用

UVA1223 Editor

给定文本字符串 s，查找文本字符串 s 中最长的子字符串，使得子字符串至少出现两次。

对于出现两次的子串，一定是后缀排序后相邻的两个的公共前缀，答案即为对 height 数组取最大值。

void solve() {
    int ans = -1;
    scanf("%s", s + 1);
    n = strlen(s + 1);
    m = 122;
    for(int i = 1; i <= m; i ++) sa[i] = rk[i] = c[i] = height[i] = x[i] = y[i] = 0;
    get_sa();
    get_height();
    for(int i = 1; i <= n; i ++) ans = max(ans, height[i]);
    cout << ans << endl;
}
int main() {
    int T;
    cin >> T;
    while(T --) {
        solve();
    }
}

P2408 不同子串个数

不同字串的个数就是所有的字串减去相同的字串个数。总的字串个数为 \frac{n(n + 1)}{2} 。所有后缀产生的相同的前缀个数为 \sum_{1}^{n} height[rk[i]]，相同的字串个数为 \sum_{1}^{n} height[rk[i]]。答案为 \frac{n(n+1)}{2} - \sum_{1}^{n} height[rk[i]]。