后缀数组之倍增算法

后缀数组(Suffix Array,SA)可以通过预处理文本串,解决多模板匹配问题。

而AC自动机正好相反,需要事先知道所有的模板。

这是需要首先注意的。

后缀数组

定义字符串的后缀的编号为首字母在原串中的位置。

后缀数组的定义:将字符串的所有后缀排序,其编号构成的数组称为后缀数组

相比后缀自动机和后缀树,后缀数组更为简单,所以更为常用

后缀数组的构造

常使用倍增算法构造后缀数组

其思想是名次的大小体现了子串的大小,将两个名次当作二元组排序。

参与排序的子串长度倍增,最终变成全串的后缀

首先对所有后缀的第一个字符排序:(图片来自网络)

将得到的名次两两绑定再排序:

得到的名次再排序:

此时每个元素已经代表4个后缀了,依次类推便可将所有后缀排序,排名不变动表示排序已完成

这样倍增的次数是\(O(logn)\)的,如果每次使用基数排序,复杂度为\(O(nlogn)\)

还是比较强大的。

这里提供两个模板:

1.用vector模拟基数排序,便于理解但常数大

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
vector<int> buc[maxn];
int rk[maxn*2],res[maxn],id[maxn];
void csort(int k){
for (int i=0;i<=m;i++) buc[i].clear();
for (int i=1;i<=n;i++) buc[rk[id[i]+k]].push_back(id[i]);
id[0]=0;
for (int i=0;i<=m;i++){
int len=buc[i].size();
for (int j=0;j<len;j++) id[++id[0]]=buc[i][j];
}
}
void make_sa(){
m=128;
for (int i=1;i<=n;i++) rk[i]=s[i];
for (int k=1;k<n;k<<=1){
for (int i=1;i<=n;i++) id[i]=i;
csort(k); csort(0);
id[0]=0; int t=0;
for (int i=1;i<=n;i++){
if (!(rk[id[i]]==rk[id[i-1]]&&rk[id[i]+k]==rk[id[i-1]+k])) t++;
res[id[i]]=t;
}
for (int i=1;i<=n;i++) rk[i]=res[i];
if (t>=n) break;
m=t;
}
for (int i=1;i<=n;i++) sa[rk[i]]=i;
}

2.每次倍增都更新SA,通过叠加得到名次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int rk[maxn],t[maxn],buc[maxn];
void get_sa(){
cl(buc,0);
for (int i=1;i<=n;i++) buc[rk[t[i]]]++;
for (int i=1;i<=m;i++) buc[i]+=buc[i-1];
for (int i=n;i>=1;i--) sa[buc[rk[t[i]]]--]=t[i];
}
void make_sa(){
m=128;
for (int i=1;i<=n;i++) rk[i]=s[i],t[i]=i;
get_sa();
for (int k=1;k<n;k<<=1){
int p=0;
for (int i=n-k+1;i<=n;i++) t[++p]=i;
for (int i=1;i<=n;i++) if (sa[i]>k) t[++p]=sa[i]-k;
get_sa(); t[sa[1]]=p=1;
for (int i=2;i<=n;i++)
if (rk[sa[i]]==rk[sa[i-1]]&&rk[sa[i]+k]==rk[sa[i-1]+k]) t[sa[i]]=p;else t[sa[i]]=++p;
memcpy(rk,t,sizeof(t));
if (p==n) break;
m=p;
}
}

后缀数组的应用

多模板匹配

由于已经得到了所有后缀的排序,可以直接二分,验证这个后缀是否比模板串大

如果模板串是一个后缀的前缀,就说明模板串是文本串的子串,二分得到的上下界一减就知道匹配了几次

时间复杂度\(O(mlogn)\),m是模板串长度

求LCP

\(height[i]\)表示串\(sa[i]\)与串\(sa[i-1]\)的LCP

那么\(sa[i]\)\(sa[j]\)两个后缀的LCP就等于\(\mathop{Max} \limits^j_{k=i+1}\{ height[sa[k]] \}\)

其实求LCP就转化为RMQ问题了


如何求\(height\)呢?

\(h[i]=height[rank[i]]\)

那么就有这样一个性质: \[ h[i]\ge h[i-1]-1 \]

证明如下:

\(rank[k]=rank[i-1]-1\),则\(h[i-1]=LCP\{i-1,k\}\)

那么将这两个后缀去掉第一个字符,得到后缀\(k+1\)\(i\)

其实\(h[i-1]-1=LCP\{k+1,i\}\),而此时\(rank[k+1]\le rank[i]-1\)

所以\(h[i]\ge h[i-1]-1\)

利用这个性质,每次用\(h[i-1]\)就可以推出\(h[i]\),再得到\(height[i]\),复杂度\(O(n)\)

代码如下,很简单:

1
2
3
4
5
6
for (int i=1,h=0;i<=n;i++){
if (h) h--;
int j=sa[rk[i]-1];
while (s[i+h]==s[j+h]) h++;
ht[rk[i]]=h;
}

求第K大子串

考虑后缀\(sa[i]\)能够提供\(n-sa[i]+1-height[i]\)个本质不同的子串

用二分看第K个子串落在哪个后缀中就好了

相同子串算多个:

这个只能\(O(nlogn)\)回答了,BZOJ3998

二分这个子串是哪个后缀的前缀

只要知道有多少子串比当前后缀小即可

排名更前的任意子串都比它小,贡献\(\sum n-sa[i]+1\)

排名更后的其实就是LCP会比它小,贡献\(\sum_i LCP(sa[i],sa[mid])\)

求子串Rank

直接二分找到第一个含该子串的后缀,然后

\(n-sa[i]+1-height[i]\)的前缀和,就能得到比该子串小的个数了

子串是哪些后缀的前缀

显然答案是一个连续的区间(rank连续)

假设求子串\(S_{a,b}\),首先得到\(rank[a]\),答案就是向两边扩展一下

可以发现答案区间内所有后缀与后缀a的LCP一定大于等于\(b-a+1\)

预处理关于\(height\)的ST表,直接倍增一下得到这个区间

子串是否包含另一个子串

假设询问子串\(S_{a,b}\)是否包含子串\(S_{c,d}\)

可以知道子串\(S_{c,d}\)是哪些后缀的前缀,这些后缀的排名是连续的

只要出现某个后缀的开头属于\([a,b-(d-c+1)+1]\)就有了

相当于在区间内询问是否有值属于某区间,主席树维护就好了

暂时先写这么多,想到再补……