阅读数 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;
}