好像非常好用

本来SDOI2018之前不想学什么新东西来着…sign…

感谢Menci爷爷的blog

沙茶的 SA不详解

SA用来解决一些字符串的问题, SA最基本的应用就是求出一个字符串的每一个后缀的排名

也就是优化了一个$n^2\lg n$的暴力排序

$SA$的主要思想就是尽可能的利用[后缀]这一特殊的性质, 减少不必要的计算

我们发现, 在计算后缀的排名时, 是从前向后比较的(废话: 当然是先比较前面的, 如果相等才去看后面的), 那么我们发现, 在一个字符串中, 如果已经求出长度为$length$的后缀的排名, 那么我们就可以按照双关键字排序求出长度为$length << 1$的所有后缀的排名, 因为后缀的性质保证了

一个长度为$length << 1$的后缀的后半段一定是一个长度为$length$的后缀

所以我们在求完长度为$length$的所有后缀的排名时, 已经把所有长度为$length << 1$的后缀的前半段和后半段的排名都求出来了, 只需要按照双关键字排一下序就可以了, 直接sort的复杂度是$\mathrm O(n \lg^2 n)$的, 一般是过不了$10^6$的数据的MHR: 谁说过不了? 我还抢了最优解! 所以我们需要一种$\mathrm O(n)$的方法, 也就是要求双关键字排序的复杂度为$\mathrm O(n \lg n)$, 于是我们找到了桶排…

具体实现还是挺妙的…他求出了当前长度的每一个后缀的前半段(fir)和后半段(sec)后, 记录一下第i大的是哪个后缀(的开头), 即tmp, 然后sa再在前半段相同的时候, 按照tmp给定的顺序排序(即在桶中一个数的个数不为1的时候按照tmp赋排名), 然后每一遍倍增结束后, 就更新sarank, 如果发现还有并列排名的后缀, 继续迭代, 否则直接退出(这时候肯定已经排好序了, 再排也没什么意思了)

还是老老实实背板子吧

height明天再说

沙茶的超大常数跑不过MHR暴力的 代码

具体实现可以看一下注释

据说sa赋值不是很好懂? 那我再说一遍…

j1开始枚举, 也就是保证了开头为i的后缀排名始终是没排好序中的所有后缀中最靠后的, 而tong[fir[i]]--, 就是按照以i开头的后缀的前半段fir排序, 又重复的fir再按照后半段sec排序, 可以考虑参悟或者意会一下…

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000000 + 5)
using namespace std;
char s[MAXN], sors[MAXN];
int sa[MAXN], rnk[MAXN], n, ts[MAXN]; // sa[i]: 排名为i的后缀开头是sa[i]; 开头是i的后缀排名为rnk[i]
void initsa();
int main()
{
    scanf("%s", s);
    n = strlen(s);
    initsa();
    for (int i = 1; i <= n; i++)
        printf("%d ", sa[i]);
    return 0;
}
void initsa()
{
    static int tong[MAXN], fir[MAXN], sec[MAXN], tmp[MAXN];
    strcpy(sors, s);
    sort(sors, sors + n);
    int tn = unique(sors, sors + n) - sors;
    for (int i = 1; i <= n; i++)
        ts[i] = lower_bound(sors, sors + tn, s[i - 1]) - sors + 1;
    for (int i = 1; i <= n; i++)    ++tong[ts[i]];
    for (int i = 1; i <= n; i++)    tong[i] += tong[i - 1]; // 直接获取排名
    for (int i = 1; i <= n; i++)    rnk[i] = tong[ts[i] - 1] + 1; // 这里的 -1 +1 可以保证a[i]是在相同大小的数中排名第一, 而非最后
    for (int t = 1; t <= n; t <<= 1)
    {
        for (int i = 1; i <= n; i++)    fir[i] = rnk[i]; // 直接把前半段变成一个数, 因为前半段已经排好序了, 不必再比较一遍, 直接按照他的排名排就可以啦 
        for (int i = 1; i <= n; i++)    sec[i] = ((i + t) > n ? 0 : rnk[i + t]); // 后半段

        fill(tong, tong  + n + 1, 0); // 用fill代替桶可以尽量避免大数组memset造成的时间浪费
        for (int i = 1; i <= n; i++)    ++tong[sec[i]];
        for (int i = 1; i <= n; i++)    tong[i] += tong[i - 1]; // 求出每一个以i开头的后缀的后半段的排名
        for (int i = 1; i <= n; i++)    tmp[n - --tong[sec[i]]] = i; // tmp[i]: 第i大的是开头为tmp[i]的后缀

        fill(tong, tong + n + 1, 0);
        for (int i = 1; i <= n; i++)    ++tong[fir[i]];
        for (int i = 1; i <= n; i++)    tong[i] += tong[i - 1];
        for (int j = 1, i; j <= n; j++)    i = tmp[j], sa[tong[fir[i]]--] = i; // 从大到小赋值, 保证了前半段同一大小的情况下按照后半段排序; 注意, sa的下标是排名

        bool ok = true;
        for (int j = 1, i, last = 0; j <= n; j++)
        {
            i = sa[j]; // i是排名为j的后缀的开头 
            if (!last)    rnk[i] = 1; // 如果i是排名第一的后缀的开头, 直接赋成1 
            else    if (fir[i] == fir[last] && sec[i] == sec[last])    rnk[i] = rnk[last], ok = false; // 有两个后缀在目前长度重复的情况, 把排名赋成与他重复的那个后缀的排名 
            else    rnk[i] = rnk[last] + 1; // 否则, 既然比上一个大, 就把排名赋成上一个的排名 + 1 
            last = i; // "现在的"变成了下一次迭代的"上一个 " 
        }
        if (ok)
            break; // 在当前状态下就已经没有了重复, 因为是从前向后比较的, 所以后面的也没有比较的必要了, 排名已经确定, 直接退出 
    }
}

/*
ababa
*/

By 啥都不会的 沙茶Cansult