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

后缀数组入门

sa和rk的计算

rk表示第i个后缀(第i个位置后面的元素)的排名
sa为其逆函数,即排名i的后缀,所在位置
upd:其实并不完全是逆函数,因为rk允许重复,需要压缩相同的值

采用倍增给后缀排序
然后多关键字的话,非常巧妙地方法:先第二关键字,然后用稳定排序来第一关键字(类似覆盖)

height的计算

height[i]=LCP(后缀排名i-1,后缀排名i)
如果能计算出这个东西,那么询问任意两个后缀的LCP就是询问区间height最小值

然后现在希望尽量快地计算出height,那和所有字符串算法一样,尽可能地优化总势能
考虑定义的特性,字典序的排名有什么性质?
通过上面利用height的方式得到启发,任意两个串的LCP能保证中间的LCP的下限

具体性质: $height[rk[i]] \geq height[rk[i-1]]-1$
$a=i-1,b=sa[rk[i-1]-1]$
$c=i,d=sa[rk[i]-1]$
现在要证明 $LCP(c,d) \leq LCP(a,b)-1$
然后只考虑 $LCP(a,b) \leq 2$ 的情况,否则显然
c就是a去掉了开头的一个字符,设e=b+1(去头)
$LCP(e,c)=LCP(a,b)-1$
然后因为是字典序,e依然会在c前面,得证

按照这个做,时间复杂度就是2n的

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
struct Sa
{
int rk[MAX_N*2],sa[MAX_N*2],hei[MAX_N*2];
int ct[MAX_N*2],tmp[MAX_N*2],wr[MAX_N*2];
void getsa()
{
memset(ct,0,sizeof ct);
for(int i=1;i<=n;i++) ct[rk[i]=a[i]]++;
for(int i=1;i<MAX_N;i++) ct[i]+=ct[i-1];
for(int i=n;i>=1;i--) sa[ct[rk[i]]--]=i;
int ln=1;
while(ln<n)
{
int tot=0;for(int i=1;i<=n;i++) if(sa[i]+ln>n) tmp[++tot]=sa[i];
for(int i=1;i<=n;i++) if(sa[i]-ln>=1) tmp[++tot]=sa[i]-ln;
memset(wr,0,sizeof wr);//debug
memset(ct,0,sizeof ct);
for(int i=1;i<=n;i++) ct[ wr[tmp[i]]=rk[tmp[i]] ]++;
for(int i=1;i<MAX_N;i++) ct[i]+=ct[i-1];
for(int i=n;i>=1;i--) sa[ct[wr[tmp[i]]]--]=tmp[i];
int cnt=1;rk[sa[1]]=1;
for(int i=2;i<=n;i++)
{
if(wr[sa[i-1]]!=wr[sa[i]] or wr[sa[i-1]+ln]!=wr[sa[i]+ln]) cnt++;
rk[sa[i]]=cnt;
}
ln*=2;
}
}
void gethei()
{
int lst=0;
for(int i=1;i<=n;i++)
{
if(rk[i]==1) {hei[1]=0;continue;}
int j=sa[rk[i]-1];if(lst) lst--;
while(max(i,j)+lst<=n and a[i+lst]==a[j+lst]) lst++;
hei[rk[i]]=lst;
}
}
}sa;

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