单字符串问题

概述

后缀数组(suffix array),计算的是一个字符串的所有后缀经过字典排序后的起始下标结果。

S = banana$

其中,名次数组 Rank[i] 保存的是起始位置为 i 的后缀在所有后缀中从小到大排列的 名次

倍增算法

  1. 对长度为 \(2^0=1\)的字符串,也就是所有单字母排序。
  2. 用长度为 \(2^0=1\)的字符串,对长度为 \(2^1=2\)的字符串进行双关键字排序。考虑到时间效率,我们一般用基数排序。
  3. 用长度为 \(2^{k-1}\)的字符串,对长度为 \(2^k\)的字符串进行双关键字排序。
  4. 直到 \(2^k\geq n\),或者名次数组 Rank 已经从 1 排到 n,得到最终的后缀数组。
    以字符串aabaaaab为例, 整个过程如下图所示。其中 x,y 表示长度为 \(2^k\)的字符串的两个关键字。

参考代码

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
const int MAX_LEN = 200010;
int r[MAXN]; // r 数组保存了字符串中的每个元素值,除最后一个元素外,每个元素的值在 1..m 之间,最后一个元素的值为 0
int wa[MAXN], wb[MAXN], wv[MAXN], ws[MAXN]; // 这 4 个数组是后缀数组计算时的临时变量,无实际意义
int sa[MAXN]; // sa[i] 保存第 i 小的后缀在字符串中的开始下标,i 取值范围为 0..n-1
int cmp(int *r, int a, int b, int l) {
return r[a] == r[b] && r[a + l] == r[b + l];
}
void da(int *r, int *sa, int n, int m) { // n 为字符串的长度,m 为字符最大值
int i, j, p, *x = wa, *y = wb;
for (i = 0; i < m; ++i) ws[i] = 0;
for (i = 0; i < n; ++i) ws[x[i] = r[i]]++;
for (i = 1; i < m; ++i) ws[i] += ws[i - 1];
for (i = n - 1; i >= 0; --i) sa[--ws[x[i]]] = i;
for (j = 1, p = 1; p < n; j *= 2, m = p) {
for (p = 0, i = n - j; i < n; ++i) y[p++] = i;
for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
for (i = 0; i < n; ++i) wv[i] = x[y[i]];
for (i = 0; i < m; ++i) ws[i] = 0;
for (i = 0; i < n; ++i) ws[wv[i]]++;
for (i = 1; i < m; ++i) ws[i] += ws[i - 1];
for (i = n - 1; i >= 0; --i) sa[--ws[wv[i]]] = y[i];
for (swap(x, y), p = 1, x[sa[0]] = 0, i = 1; i < n; ++i)
x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;
}
return;
}

Height数组

令 \(height[i]\) 是 \(suffix(sa[i-1])\) 和 \(suffix(sa[i])\) 的最长公共前缀,即排名相邻的两个后缀的最长公共前缀。

性质:若 rank[j] < rank[k],则后缀 \(S_{j..n}\)和 \(S_{k..n}\)的最长公共前缀为 \(min \{ height[rank[j]+1],height[rank[j]+2]…height[rank[k]] \} \)。

怎样计算 \(height\) 数组?

$$ \displaystyle height[i] \geq height[i-1]-1 $$

按照 \(height[1], height[2] … height[n]\) 的顺序计算,时间复杂度可以降为 \(\mathcal{O}(n)\)。

1
2
3
4
5
6
7
8
9
10
int rank[MAXN];  // rank[i] 表示从下标 i 开始的后缀的排名,值为 1..n
int height[MAXN]; // 下标范围为 1..n,height[1] = 0
void calHeight(int *r, int *sa, int n) {
int i, j, k = 0;
for (i = 1; i <= n; ++i)
rank[sa[i]] = i;
for (i = 0; i < n; height[rank[i++]] = k)
for (k ? k-- : 0, j = sa[rank[i] - 1]; r[i + k] == r[j + k]; ++k);
return;
}

例 1:可重叠最长重复子串

给定一个字符串,求最长重复子串,这两个子串可以重叠。

  • 题目解析

重复子串即两后缀的公共前缀,最长重复子串,等价于两后缀的最长公共前缀的最大值。

只需计算 height 数组,再比较得到最大值,就是最长重复子串的长度。

例 2:不可重叠最长重复子串

给定一个字符串,求最长重复子串,这两个子串不能重叠。

  • 题目解析

直接用 height 数组不能保证两后缀不重叠,可二分答案,变成判定性问题。

现在问题转化为:原串中是否有长度为 k 的重复子串。

按 height 数组把后缀分组,每组的 height 值都 \( \geq k\)。若存在至少一组,后缀的前起始点和后起始点的差 \(\geq k\),或者说 \(SA_{max}-SA_{min}\geq k\),则存在长度为 k 的重复子串。

时间复杂度:\(\mathcal{O}(nlogn)\)。

例 3:最长 k 次重复子串

给定一个字符串,求至少出现 k 次的最长重复子串,这 k 个子串可以重叠。

  • 题目解析

这题的做法和上题类似,先二分答案,然后将后缀分成若干组。不同点在于,这里要判断的是有没有一个组的后缀个数不小于 k。如果有,那么存在 k 个相同的子串满足条件,否则不存在。

时间复杂度:\(\mathcal{O}(nlogn)\)。

例 4:不同子串的个数

给定一个字符串,求不相同的子串的个数。

  • 题目解析

容易想到,按后缀 \(sa[1], sa[2], sa[3] \ldots sa[n]\) 的顺序考虑,sa[i] 与前面后缀相同的子串个数,也就是 sa[i] 与 sa[i-1] 相同的子串个数,也就是 height[i] 个,所以由可能的子串数 \(n - sa[i] + 1\) 去掉 height[i] 即可。原问题转化为对 n - sa[i] + 1 - height[i] 求和。

更新记录

  • 2018年08月31日 单字符串问题