概述

后缀数组(Suffix Array)是处理字符串问题的有力工具
其记录了字符串的所有后缀,以字符串banana$($为字符串结尾)为例
将其所有后缀按字典序排序

Suffix i
$ 7
a$ 6
ana$ 4
anana$ 2
banana$ 1
na$ 5
nana$ 3

sa[1] = 7,sa[2] = 6 …

然后顺便记录名次数组,rk[i]表示后缀i在sa中的名次,与sa互为反函数
rk[7] = 1,rk[6] = 2 …

令height[i] 表示 suffix(sa[i])和suffix(sa[i-1])的 LCP 长度
height[2] = 0,height[3] = 1,height[4] = 3

  • 若rk[j] < rk[k],则后缀 $S_{j…n}$ 和 $S_{k…n}$的 LCP 长度为 min{height[rk[j]+1],…,height[rk[k]]}

这个性质是显然的,因为后缀已经按字典序排序

  • height[rk[i]] >= height[rk[i-1]] - 1

设 suffix(k) 为排在 suffix(i-1) 前一名的后缀,那么它们的LCP长度为 height[rk[i-1]]
suffix(k+1) 将排在 suffix(i) 前一名(默认height[rk[i-1]] > 1,否则原式显然成立)
且 suffix(k+1) 与 suffix(i) 的LCP为 height[rk[i-1]] - 1
因此suffix(i)与之前一名的LCP至少为 height[rk[i-1]] - 1

模板

实现方式为倍增

  • 对于长度为 $2^0 = 1$ 的字符串也就是所有单字母排序
  • 用长度为 $2^0 = 1$ 的字符串,对长度为 $2^1 = 2$ 的字符串进行双关键字(基数)排序
  • 用长度为 $2^{k-1}$ 的字符串,对长度为 $2^k$ 的字符串进行双关键字排序
  • 直到$2^k \geq n$,或rk数组以及从 1 排到 n,得到最终的后缀数组

SA

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
const int maxn = 1e5 + 10;
const int maxc = 256;

int cntA[maxn],cntB[maxn],A[maxn],B[maxn],tsa[maxn];
int sa[maxn],rk[maxn],height[maxn];
char ch[maxn];

void SA()
{
memset(cntA,0,maxc*sizeof(int));
for(int i=1;i<=n;++i) cntA[ch[i]]++;
for(int i=1;i < maxc;++i) cntA[i] += cntA[i-1];
for(int i=n;i;--i) sa[cnt[ch[i]] --] = i;
rk[sa[1]] = 1;
for(int i=2;i<=n;++i)
{
rk[sa[i]] = rk[sa[i-1]];
if(ch[sa[i]] != ch[sa[i-1]]) rk[sa[i]] ++;
}
for(int l=1;rk[sa[n]] < n; l <<= 1)
{
memset(cntA,0,sizeof(cntA));
memset(cntB,0,sizeof(cntB));
for(int i=1;i<=n;++i)
{
cntA[A[i] = rk[i]]++;
cntB[B[i] = (i+l <=n)?rk[i+1]:0]++;
}
for(int i=1;i<=n;++i) cntB[i] += cntB[i-1];
for(int i=n;i;--i) tsa[cntB[B[i]]--] = i;
for(int i=1;i<=n;++i) cntA[i] += cntA[i-1];
for(int i=n;i;--i) sa[cntA[A[tsa[i]]]--] = tsa[i];
rk[sa[1]] = 1;
for(int i=2;i<=n;++i)
{
rk[sa[i]] = rk[sa[i-1]];
if(A[sa[i]] != A[sa[i-1]] || B[sa[i]] != B[sa[i-1]]) rk[sa[i]]++;
}
}
for(int i=1,j=0;i<=n;++i)
{
if(j) --j;
while(ch[i+j] == ch[sa[rk[i]-1]+j]) ++j;
height[rk[i]] = j;
}
}

题目

查询两后缀的LCP

转化为height数组上RMQ求最小值

求最长的子串,在串中至少重复了k次

可重叠

子串即等价于两后缀的LCP
现在问题即转化为了
使长度至少为k-1的height连续子序列的最小值最大

用滑窗+单调队列解决即可

不可重叠

题目中对于序列加上或减去一个整数也视为等价
我们对相邻两元素做差,当前序列答案+1即为原序列答案

二分一个长度l,转为判定问题
很明显若存在连续地height数组值都大于等于l
且其中距离最远的两个后缀位置的差值大于等于l
则说明存在长度为l的不重叠子序列

不同子串个数

我们按照 suffix(sa[1]),suffix(sa[2]),… 的顺序来计算

每个后缀会产生 n-sa[i]+1 个新的前缀,其中 height[i] 个前缀与前一个字符串前缀相同
因此 suffix(sa[i]) 的贡献为 n-sa[i]+1-height[i] 累加起来即为答案

最长回文子串

将串旋转后加入尾部,中间间隔一个特殊字符

枚举每一位,求其作为中心位置的最长回文子串,即求一个后缀和一个反过来的后缀的LCP
对于奇偶分两种情况,如下图所示

sa2lps

复杂度$O(nlogn)$ (RMQ的复杂度)

当然有 $O(n)$ 的 manacher

连续重复子串

给定一个字符串L,已知这个字符串由某个字符串S重复R次得到,求R的最大值

枚举字符串S长度k,然后判断是否满足。
判断的时候先看L能否被k整除,然后看suffix(1)和suffix(k+1)的lcp是否等于n-k
由于suffix(1)是固定的,因此扫一遍预处理height数组中每个数到 height[rk[1]] 的最小值即可

复杂度 $O(n)$

p.s. 注意这题规模达到1e7…倍增的后缀数组会TLE…正解是KMP

重复次数最多的连续重复子串

枚举长度s,然后从每一个位置判断

复杂度 $O(nlogn)$

最长公共子串

将两个字符串连接,中间以特殊字符分隔
答案为 suffix(sa[i]) 与 suffix (sa[i-1]) 不是同一个字符串中的后缀时的最大值

长度不小于k的公共子串个数

将两个字符串连接,中间以特殊字符分隔
扫描 height 数组
若当前为A的后缀,则统计其与之前所有的B的后缀的lcp >= k的个数
若当前为B的后缀,则统计其与之前所有的A的后缀的lcp >= k的个数
这个过程可以用单调栈分别维护A和B的height
(详见代码…)

多个字符串求不小于k个字符串中的最长子串

题意为求至少在一半字符串中出现的最长公共子串

将n个字符串连起来,中间用不相同的且没有出现在字符串中的字符隔开
然后二分公共子串长度,判断其是否出现在超过一半的串

每个字符串至少出现两次且不重叠的最长子串

和上题的做法差不多,区别在判断的时候

出现或反转后出现在每个字符串中的最长子串

和上题做法差不多,只需要将串的反转也加入即可

参考