后缀数组与相关应用
command_block
2019-04-26 21:49:26
显而易见,这是个大坑,不是省选前能够写完的。
先随便写一点吧,毕竟自己的字符串题太弱了……
## 很抱歉,这篇文章鸽了。
# 1.后缀数组与其实现
字符串匹配问题中最常见的就是“子串”。
考虑子串的本质:某一个后缀的前缀。
当我们在一个静态数组里面进行查找的时候,一个很经典的套路就是对这个数组进行排序,然后使用二分查找。
对于一个字符串匹配问题,我们可以把所有的后缀按照字典序排序,然后和模式串大力匹配,则可做到一个优秀的复杂度。
怎么排序呢?直接sort+暴力比较即可做到$O(n^2logn)$
或者使用Trie即可做到$O(n^2)$。
使用Hash优化快排的比较可以达到$O(nlog^2n)$ ,即所谓的$Dark-SA$。
(但是常数过大,一般不使用)
我们考虑采用倍增的思想解决问题。
设$rk^p[i]$表示从第$i$位开始的长度为$2^p$的后缀的排名,如果串末不足用0补(字典序最小)。
$rk^{(p+1)}$可以从$rk^p$转移过来。
按照$(rk^{p}[i],rk^{p}[i+(1<<p)])$这一组pair排序,就可以得到$rk^{(p+1)}$,根据人类直觉是对的。
具体实现就是$O(logn)$次排序,如果使用快排可以做到$O(nlog^2n)$。
如果采用基数排序$O(nlogn)$。
这里有一个明显的小trick:如果$rk$已经互不相同则可以停止排序,在随机数据中表现非常优秀。
快排版:
加了上述剪枝,由于数据随机是可以过的。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#define MaxN 1005000
using namespace std;
char s[MaxN];
int n,len;
struct Data
{int a,b,pos;}
t[MaxN];
bool cmp(Data A,Data B)
{return A.a==B.a ? A.b<B.b : A.a<B.a;}
int rk[MaxN],sa[MaxN];
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
for (int i=1;i<=n;i++)rk[i]=s[i];
len=1;
while(len<=n){
for (int i=1;i<=n;i++){
t[i].a=rk[i];
t[i].b=(i+len>n) ? 0 : rk[i+len];
t[i].pos=i;
}sort(t+1,t+n+1,cmp);
int p=0;bool flag=1;
for (int i=1;i<=n;i++){
if (t[i].a!=t[i-1].a||t[i].b!=t[i-1].b)
p=i;
else flag=0;
rk[t[i].pos]=p;
}if (flag)break;
len<<=1;
}for (int i=1;i<=n;i++)sa[rk[i]]=i;
for (int i=1;i<=n;i++)printf("%d ",sa[i]);
return 0;
}
```
[AC记录](https://www.luogu.org/recordnew/show/18558856)
基排版:
比上面快一个$log$,也就快了400ms……
我的基排是八倍大常数，听说有更快的方法，懒得研究了，反正没听说过卡倍增的。
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#define MaxN 1005000
using namespace std;
char s[MaxN];
int n,len;
struct Data
{int a,b,pos;}
t[MaxN],sav[MaxN];
int rk[MaxN],sa[MaxN];
int *e=sa;
void fsort()
{
for (int i=1;i<=n;i++)e[i]=s[i];
sort(e+1,e+n+1);
for (int i=1;i<=n;i++)
rk[i]=lower_bound(e+1,e+n+1,s[i])-e;
}
int *o=sa;
void qsort()
{
for (int i=0;i<=n;i++)o[i]=0;
for (int i=1;i<=n;i++)o[t[i].b+1]++;
for (int i=1;i<=n;i++)o[i]+=o[i-1];
for (int i=1;i<=n;i++)sav[++o[t[i].b]]=t[i];
for (int i=0;i<=n;i++)o[i]=0;
for (int i=1;i<=n;i++)o[sav[i].a+1]++;
for (int i=1;i<=n;i++)o[i]+=o[i-1];
for (int i=1;i<=n;i++)t[++o[sav[i].a]]=sav[i];
}
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
fsort();
len=1;
while(len<=n){
for (int i=1;i<=n;i++){
t[i].a=rk[i];
t[i].b=(i+len>n) ? 0 : rk[i+len];
t[i].pos=i;
}qsort();
int p=0;bool flag=1;
for (int i=1;i<=n;i++){
if (t[i].a!=t[i-1].a||t[i].b!=t[i-1].b)
p=i;
else flag=0;
rk[t[i].pos]=p;
}if (flag)break;
len<<=1;
}for (int i=1;i<=n;i++)sa[rk[i]]=i;
for (int i=1;i<=n;i++)printf("%d ",sa[i]);
return 0;
}
```
# 2.相关定理与工具
谈到后缀数组，就不得不说$hight$数组了，这是一个强有力的工具。
$hight[i]$表示$suf[sa[i]]$和$suf[sa[i+1]]$的最长公共前缀长度。
这里有两个定理：
1.$lcp(suf[sa[i]],suf[sa[j]])=\min\limits_{p=i}^{j-1}hight[p]$
可以吧$hight$理解为后缀树上的$lca$深度，那么一个区间节点的$lca$深度就是他们两两之间最浅的那个（待证明）。
2.$h[rk[i+1]]>=h[rk[i]]-1$
也就是说在原串中相邻的两个后缀，它们的$hight$不会相差的太大。
证明：
1)$h[rk[i]]<=1$此时得到$h[rk[i+1]]>=0$,不证自明。
2)$h[rk[i]]>1$
```cpp
abaaca suf[i]
abacba suf[sa[rk[i]-1]]
(h[rk[i]]=3)
baaca suf[i+1]
.
.
bacba suf[sa[rk[i]-1]+1]
(h[rk[i-1]]>=3-1)
```
我们知道$lcp(suf[i+1],suf[sa[rk[i]-1]+1])=2$由定理1可得,他们之间的$hight$都大于2，证毕。
**应用:**
定理1搭配ST表食用。
定理2用于求$hight$:
我们按照$h[rk[1...n]]$的顺序来求，则可以利用定理2，每次$h$的值最多下降1，类似蜗牛爬杆，复杂度$O(n)$。
（当然如果你记不住的话直接$Hash$+二分也可以，所谓$Dark-hight$）