【OI之路】10字符串-6后缀数组

一句精辟的话:字符串相关算法就是用来偷懒的 ——scy

更详细地解释:Manacher、莫队、fft、后缀数组、exkmp等各种算法,本质上都是尽量地利用子信息、残留信息

8.1 定义

sa[i]=j 排第i的是原字符串中(假设他是s[])s[j]为开头的后缀
rk[i]=j 在原字符串中s[i]排第j
y[i]=j 因为后面要补0(跟sa数组的记录方式一样,都是记录开头)
wr[i]=j 对第二关键字排序后的rank值
rsort[i]=j 基数排序中要用到的数组,表示数字i出现了j次

基数排序构建后缀数组过程如下:

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
//*******************定义*******************
const int MAXN=210000,MAXM=210000;
int wr[MAXN],rk[MAXN],sa[MAXN],y[MAXN],rsort[MAXM];
int s[MAXN];
//*******************实现*******************
void getsa(int n,int m)
{
//基数排序
for(int i=0;i<=m;i++) rsort[i]=0;
for(int i=1;i<=n;i++) rsort[rk[i]=s[i]]++;
for(int i=1;i<=m;i++) rsort[i]+=rsort[i-1];
for(int i=n;i>=1;i--) sa[rsort[rk[i]]--]=i;
int p=0,ln=1;//不同子串量;当前子串大小
while(p<n)
{
//先按照第二关键字排序
//y[第二关键字排名]=第一关键字位置
int k=0;
for(int i=n-ln+1;i<=n;i++) y[++k]=i;
//优先第二关键字为空的情况,排名定靠前
for(int i=1;i<=n;i++) if(sa[i]>ln) y[++k]=sa[i]-ln;
//确保是第二关键字
//再使用稳定排序对第二关键字所对应的第一关键字排序
//wr[第二关键字排名]=第一关键字排名
for(int i=0;i<=m;i++) rsort[i]=0;
for(int i=1;i<=n;i++) rsort[wr[i]=rk[y[i]]]++;
for(int i=1;i<=m;i++) rsort[i]+=rsort[i-1];
for(int i=n;i>=1;i--) sa[rsort[wr[i]]--]=y[i];
//可以这样理解:既然rk[i]对应i,则rk[y[i]]对应y[i]
//既然刚才对第二关键字排序,就用这个顺序来循环
swap(wr,rk);//wr数组保存旧rank值
p=1;rk[sa[1]]=1;
for(int i=2;i<=n;i++)
{
if(wr[sa[i]]!=wr[sa[i-1]] or wr[sa[i]+ln]!=wr[sa[i-1]+ln]) p++;
rk[sa[i]]=p;
}
m=p;ln*=2;
}
for(int i=1;i<=n;i++) rk[sa[i]]=i;
}
int hei[MAXN];
void gethei(int n)
{
int ht=0;
for(int i=1;i<=n;i++)
{
if(ht) ht--;
int k2=sa[rk[i]-1];//h[i-1]-1
while(s[k2+ht]==s[i+ht]) ht++;
hei[rk[i]]=ht;
}
}

参考文档
同学的:CSDN
专业论文(已不存在:http://pan.baidu.com/s/1hs8yjac)
网络上:博客园

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/cc01.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%