后缀数组(SA)/后缀自动机(SAM)
By WyyOIer |
2021-12-13 19:49:02 /
2022-05-16 19:54:43
nan

 

引入

读入一个长度为 $n$ 的由大小写英文字母或数字组成的字符串,请把这个字符串的所有非空后缀按字典序(用 ASCII 数值比较)从小到大排序,然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 $1$ 到 $n$。 $n\le10^6$

暴力怎么做?暴力是不是,加边,加边,加边,然后,并查集查询

不难想到用 $\text{sort}$ 进行排序,但比较两个串是 $O(n)$ 的啊,于是我们可以用哈希和二分优化,复杂度 $O(n\log^2n)$。

对于一般的题目,暴力与正解往往有所关联,但是…

好了,下面正式开始介绍算法。

算法流程

我们采用的是倍增思想,如需对字符串 $s=\texttt{abcaabc}$ 排序。

首先我们先对每个后缀的前 $1$ 位进行比较,若相等则他们的排名一样。

然后比较前 $2$ 位时,我们就可以用两个 $1$ 来凑出,这样每一位就有了一个二元组,然后我们用二元组排名。

注意,如果没有完整的话就补 $0$。

然后继续比较前 $4$ 位。

这时你突然发现,好像所有位置的排名都不一样了!那么算法就结束了。

看起来十分容易理解,但是这个算法充分体现了能不能理解和能不能实现是两回事。

实现的时候,我们需要 $SA_i,x_i,y_i,c_i$ 这四个数组实现。

$SA_i$ 表示的为排名第 $i$ 的是以 $SA_i$ 为起始的后缀。

$x_i$ 表示此时第 $i$ 位的第一关键字是什么,$y_i$ 存储了第二关键字从小到大的下标,$c_i$ 一会再说。

首先我们要按前 $1$ 位排序,为了方便我们直接用 $\text{Ascii}$ 码作为权值存入桶 $c$ 中,然后做一下 $c$ 的前缀和,这样我们就先给 $SA_i$ 赋了一个初值。

然后开始循环,枚举一个 $j$ 代表当前处理了前 $j$ 位,经过处理后变为 $2j$ 位。

这里由于每一个位置可以看作是 $x,y$ 的双关键字排序,所以用一下基数排序,大致思路为先将优先级小的存入桶中(也就是排序),然后再排大的。

不难发现,最后长度不到 $j$ 的第二关键字应都为 $0$,所以它们的第二关键字应该最小。

然后我们从前往后遍历 $SA_i$,如果它的其实点大于 $j$,那么说明它也可以直接进入第二关键字。

然后利用基数排序思想,打入 $c$ 数组,重新更新一遍 $SA_i$,这样这一轮的 $SA$ 就更新完。

最后就是更新 $x$ 了,我们只需要按照上面图片的思路,看是否有两个关键字一样,如果一样就用一样的编号,否则用更大的编号。

如果最后给 $x$ 的编号总数已经到达 $n$,算法结束,退出。

代码

如果上文介绍没有特别清晰,请读者一定要结合代码仔细分析和思考,看透算法的本质。

本代码可解决 $\text{Luogu P3809}$

#include 
using namespace std;
const int maxn = 2000005;
int n, m = 128;
char s[maxn];
int x[maxn], y[maxn], c[maxn], tmp[maxn], top, p;
int SA[maxn], height[maxn], rk[maxn];

int main() {
    scanf("%s", s);
    n = strlen(s);
    n++;
    for(int i = 0;i < n;i++) {
        x[i] = s[i];
        c[x[i]]++;
    }

    for(int i = 1;i < m;i++) {
        c[i] += c[i - 1];
    }

    for(int i = 0;i < n;i++) {
        SA[--c[x[i]]] = i;
    }

    for(int j = 1;j <= n;j <<= 1) {
        top = 0;
        for(int i = n - j;i < n;i++) {
            y[top++] = i;
        }

        for(int i = 0;i < n;i++) {
            if(SA[i] >= j) {
                y[top++] = SA[i] - j;
            }
        }

        for(int i = 0;i < m;i++) {
            c[i] = 0;
        }

        for(int i = 0;i < n;i++) {
            c[x[y[i]]]++;
        }

        for(int i = 1;i < m;i++) {
            c[i] += c[i - 1];
        }

        for(int i = n - 1;i >= 0;i--) {
            SA[--c[x[y[i]]]] = y[i];
        }

        for(int i = 0;i < n;i++) {
            tmp[i] = x[i];
        }

        p = 1;
        x[SA[0]] = 0;
        for(int i = 1;i < n;i++) {
            if(tmp[SA[i - 1]] == tmp[SA[i]] && tmp[SA[i - 1] + j] == tmp[SA[i] + j]) x[SA[i]] = p - 1;
            else x[SA[i]] = p++;
        }

        if(p >= n) break;
        m = p;
    }

    n--;
    for(int i = 1;i <= n;i++) {
        printf("%d ", SA[i] + 1);
    }
    return 0;
}