[板子/笔记] 后缀数组

我好菜啊现在才学后缀数组qwq

Suffix Array就是把一个字符串的所有后缀排了个序。

几个用到的定义如下:

sa[i]表示排名为i的后缀在哪个位置

rk[i]表示第i个后缀的排名

buc[i]是个桶。

x[i]表示位置i的第一关键字

y[i]表示第二关键字排名为i的第一关键字位置

然后要怎么求呢?

我们用倍增的思想。

我们先随意搞出一个字符串作为例子:

N i c o n i n i

好像暴露了自己是Nico厨事实(Fake

然后我们先对每一个字符进行排序

ch N I C O N I N I
rk 3 2 1 4 3 2 3 2

首先这里排名不同的后缀已经肯定最后排名不同了。

然后我们再对二元组(rk[i],rk[i + 1])排序(没有的设做0)

ch N I C O N I N I
rk 3 2 1 4 3 2 3 2
(rk[i],rk[i + 1]) 3 2 2 1 1 4 4 3 3 2 2 3 3 2 2 0
rk’ 5 3 1 6 5 4 5 2

接下来怎么搞呢?

所以说说好的倍增咕咕咕了?(滑稽

我们对二元组(rk’[i],rk’[i + 2])排序

ch N I C O N I N I
rk’ 5 3 1 6 5 4 5 2
(rk’[i],rk’[i + 2]) 5 1 3 6 1 5 6 4 5 5 4 2 5 0 2 0
rk’’ 6 3 1 8 7 4 5 2

然后按照倍增套路后应该对(rk’’[i],rk’’[i + 4])排序然而已经有序了就不用再排了。

所以流程是这样的:

先把每个字符搞到桶里去。对桶做个前缀和(这样每个桶的个数就是这个位置的排名)。从后往前把每个字符加到sa里并把buc—(保证短的在前)。

接着对每个k,即二元组元素下标差(rk[i],rk[i + k]),n - k + 1到n的元素肯定没有第二关键字。

sa[]中按排名从高到低,如果sa[i] > k就可以作为sa[i] - k的第二关键字。

(这时y显然满了,因为sa[i]和i建立了双射关系)

向刚才的套路把buc桶排一下并把y给清空。

然后swap(x,y)因为要重建x数组。

重建时照sa来,顺便维护一下不重元素个数,如果个数和数组大小相同就是排好了。

Code

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
const int N = 1000010,C = 'z';
struct SuffixArray
{
int x[N],y[N],buc[N],sa[N],rk[N],height[N];
void build(char *S)
{
int n = strlen(S),m = C;
for(int i = 1;i <= n;i++) ++buc[x[i] = S[i]];
for(int i = 2;i <= m;i++) buc[i] += buc[i - 1];
for(int i = n;i;i--) sa[buc[x[i]]--] = i;
for(int k = 1;k <= n;k++)
{
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;
memset(buc,0,sizeof(buc));
for(int i = 1;i <= n;i++) ++buc[x[i]];
for(int i = 2;i <= m;i++) buc[i] += buc[i - 1];
for(int i = n;i;i--) sa[buc[x[y[i]]]--] = y[i],y[i] = 0;
std::swap(x,y);
x[sa[1]] = 1;num = 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 build_height(char *S)
{
int n = strlen(S),k = 0;
for(int i = 1;i <= n;i++) rk[sa[i]] = i;
for(int i = 1;i <= n;i++)
{
if(rk[i] == 1) continue;
if(k) --k;
int j = sa[rk[i] - 1];
while(j + k <= n && i + k <= n && S[i + k] == S[j + k]) ++k;
height[rk[i]] = k;
}
}
}SA;
char S[N];
int main()
{
scanf("%s",S + 1);int n = strlen(S + 1);
SA.build(S);
//SA.build_height(S);
for(int i = 1;i <= n;i++) printf("%d%c",SA.sa[i]," \n"[i == n]);
return 0;
}