后缀数组与相关应用 更新于 2026/6/29 05:13:22 作者

command_block

显而易见,这是个大坑,不是省选前能够写完的。

先随便写一点吧,毕竟自己的字符串题太弱了……

很抱歉,这篇文章鸽了。

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$已经互不相同则可以停止排序,在随机数据中表现非常优秀。

快排版:

加了上述剪枝,由于数据随机是可以过的。

#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记录

基排版:

比上面快一个$log$,也就快了400ms……

我的基排是八倍大常数，听说有更快的方法，懒得研究了，反正没听说过卡倍增的。

#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$

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$）