学习笔记_ 后缀数组 [SA]

好像非常好用

本来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排序, 可以考虑参悟或者意会一下…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#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