后缀数组

参考文章:

2009NOI 国家集训队论文——罗穗骞

代码解释

sa[i]:表示排名为i的后缀的起始位置

rank[i]:表示从i开始的后缀的排名

height[i] = LCP(suffix(sa[i-1]), suffix(sa[i])):排名为i-1和排名为i的两个后缀的最长公共前缀

h[i] = height[rank[i]]:起始位置为i的后缀和它前一名的后缀的最长公共前缀

性质:

  1. $suffix(i)$和$suffix(k)$的最长公共前缀为$height[rank[i]+1]…height[rank[k]]$中的最小值。
  2. $h[i] \geq h[i-1] - 1$

例题

给定一个字符串,求某两个后缀的最长公共前缀

性质:LCP(suffix(i), suffix(j)) = min { height[rank[i]+1], ..., height[rank[j]] }
因此可以用rmq预处理区间最小值,然后 O(1)查询

可重叠最长重复子串

重复子串:若字符串R在字符串L中至少出现两次,则称RL的重复子串
因为相邻排名的两个后缀串之间的lcp一定比不相邻的两个后缀串的lcp大,因此答案是height数组的最大值。

不可重叠最长重复字串(poj1743)

二分答案,然后按答案对height进行分组,使得同一组内的后缀串相互之间的lcp都大于等于二分的答案。
如果一组内的最大的 sa 值减去最小的 sa 值大于等于二分的答案,那么就是可行的。用并查集维护一下就好。
要注意的是,本题是对差分后的数组建后缀数组,因此首先要保证数组元素非负,然后是差分后的公共前缀的长度的意义是不同的。

可重叠的出现至少 k 次的重复子串(poj3261)

同样还是按height分组的思想。二分答案,分组后要求同一组内的后缀串数量大于等于 k,则满足条件。

本质不同的子串数量(spoj705)

$ans = \sum_{i=1}^{n}(n-sa[i]-height[i])$

最长回文子串(ural1297)

将字符串逆转后和原字符串拼接起来,拼接前要加一个从未出现过的字符在原字符串后面,这样可以防止匹配越界。
然后枚举回文串的中心点,讨论一下长度的奇偶。

连续重复子串(poj2406)

给定一个字符串$L$,已知这个字符串是由某个字符串$S$重复$R$次而得到的,求$R$的最大值。
枚举长度$k$,如果$lcp(0,0+k) == n-k$那么$k$是满足条件的,$R = \frac{n}{k}$,因此找到最小的$k$即可。
要注意字符串长度为$10^6$,直接建后缀数组是会$MLE$(因为$dp$数组爆了)。但是我们并不需要$rmq$,因为第一个参数一直为$0$,所以我们可以将$dp$数组降到一维。

重复次数最多的连续重复子串(spoj687)

给定一个字符串$L$,求$L$的所有子串中重复次数最多的连续重复子串。
枚举长度$k$,那么$s[0],s[0+k]…,s[0+nk]$,中一定有两个相邻的会被选上,但显然这不一定是两个重复子串的开头。
开头可能会在前面$k-1$个位置中。
$n + \frac{n}{2} + \frac{n}{3} + ….. = n\log n$

最长公共子串(ural1517)

给定两个字符串 $A$ 和 $B$,求最长公共子串。
将两个字符串拼接起来,中间加个从未出现的字符。排名相邻且不在同一字符串的两个后缀的 $lcp$ 的最大值为答案。

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

不小于 k 个字符串中的最长子串(pku3294)

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

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

模板

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
// build 复杂度:O(nlogn)
// 需要保证s[n]为之前没有出现过的最小的字符。必要时手动添加,或者自动'\0'。
// sa下标从1开始编号,sa[0]表示加入的最小字符'\0'
struct SA {
char s[maxn];
int sa[maxn], t[maxn], t2[maxn], c[maxn], rank[maxn], height[maxn];
int dp[maxn][30];
void build(int m, int n) { // [0,m-1]字符集, [0,n-1] 字符串
n++;
int *x = t, *y = t2;
for (int i = 0; i < m; i++) c[i] = 0;
for (int i = 0; i < n; i++) c[x[i] = s[i]]++;
for (int i = 1; i < m; i++) c[i] += c[i - 1];
for (int i = n - 1; ~i; i--) sa[--c[x[i]]] = i;
for (int k = 1; k <= n; k <<= 1) {
int p = 0;
for (int i = n - k; i < n; i++) y[p++] = i;
for (int i = 0; i < n; i++)
if (sa[i] >= k) y[p++] = sa[i] - k;
for (int i = 0; i < m; i++) c[i] = 0;
for (int i = 0; i < n; i++) c[x[y[i]]]++;
for (int i = 1; i < m; i++) c[i] += c[i - 1];
for (int i = n - 1; ~i; i--) sa[--c[x[y[i]]]] = y[i];
swap(x, y);
p = 1;
x[sa[0]] = 0;
for (int i = 1; i < n; i++)
x[sa[i]] =
y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k]
? p - 1
: p++;
if (p >= n) break;
m = p;
}
n--;
int k = 0;
for (int i = 0; i <= n; i++) rank[sa[i]] = i;
for (int i = 0; i < n; i++) {
if (k) k--;
int j = sa[rank[i] - 1];
while (s[i + k] == s[j + k]) k++;
height[rank[i]] = k; // h[i] = height[rank[i]]
}
}
void initRmq(int n) {
for (int i = 1; i <= n; i++) dp[i][0] = height[i];
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
}
int rmq(int l, int r) {
int k = 31 - __builtin_clz(r - l + 1);
return min(dp[l][k], dp[r - (1 << k) + 1][k]);
}
int lcp(int a, int b) {
// 返回起始地址为a和b的两个后缀串的lcp
a = rank[a], b = rank[b];
if (a > b) swap(a, b);
return rmq(a + 1, b);
}
} sa;