后缀数组 - 应用

最长公共前缀

定义

LCP (Longest Commom Prefix) 最长公共前缀，求两个字符串相同且最长的前缀长度。两个字符串 t 和 t 的 LCP 是最大的 k，使得 S[1…k] == T[1…k] （字符串下标从 1 开始计数）。

我们使用 lcp(i, j) 表示字符串后缀 i 和后缀 j 的最长公共前缀。

后缀数组中我们使用 sa[i] = j 表示排名第 i 的是后缀 j，现在定义 ra[] 数组，其中 ra[i] = j 表示后缀 i 的排名为 j，求出后缀数组sa[]后，通过ra[sa[i]] = i 便可获得ra[]

定义 height 数组为 height[i] = lcp(sa[i], sa[i - 1])，即第 i 名后缀与它前一名后缀的最长公共前缀，其中height[1] = 0（数组下标从 1 开始）。

如何在 O(n) 的时间复杂度内求出 height[] ?

存在如下定理 height[ra[i]] >= height[ra[i - 1]] - 1，证明如下：

• height[ra[i - 1]] <= 1 等式成立，（前者始终大于等于 0 ）
• height[ra[i - 1]] > 1，设排在后缀 i - 1 前一个的后缀为 k，现在两个字符串都去掉首字符，后缀 i - 1 变成后缀 i，后缀 k 变成后缀 k + 1，lcp(i, k + 1) 的结果只比 lcp(i - 1, k) 小 1，（除去首字符外，之前匹配的字符依然匹配）。

模板

模板

for (i = 0, k = 0; i < n; i++) {
  if (ra[i] == 0) continue; // 排名第一，跳过
  if (k) --k;
  while (s[i + k] == s[sa[ra[i] - 1] + k]) ++k;
  height[ra[i]] = k;
}
1
2
3
4
5
6

height[] 的应用

求解两子串最长公共前缀

lcp(sa(i), sa(j)) = min(height[i + 1],..., height[j])

此定理很好理解，后缀 sa(i)、sa(i + 1)、…、sa(j) 是按照字典序从小到大排序，如果 lcp(sa(i), sa(j)) = k, 那么 height[i + 1]，…，height[j] 也均大于等于k，否则必定不成立。

求出 height 数组后，任给 i, j，我们可以通过 RMQ 求出答案。

比较一个字符串的两个子串的大小关系

如果两个子串的 lcp 值等于两个子串长度的最小值，则更长的子串更大。如果 lcp 值小于两个子串长度的最小值，则子串 i 小于子串 j 等价于 ra[i] < ra[j]，其中 i、j 分别是子串的起始位置

统计不同子串的数目

长度为 n 的字符串共 n (n + 1) / 2 个子串，子串就是后缀的前缀，按照后缀从小到大排序的顺序枚举后缀，每次新增加的子串的结束位置在与上一个后缀的 lcp 之后。通过总数 - 重复子串便可得到结果。

ans = n (n + 1) / 2 - (height[2] + height[3] + ... + height[n])

至少出现 k 次的子串的最大长度（可重叠）

出现至少 k 次意味着后缀排序后有至少连续 k 个后缀以这个子串作为公共前缀。所以，求出每相邻 k 个 height 的最小值，再求这些最小值的最大值就是答案。

例题

1044. 最长重复子串

此题 k = 2，C++ 代码如下

class Solution {
public:
    string longestDupSubstring(string s) {
        SA(s);
        int k = 1;
        for (int i = 2; i < s.size(); i++) if (h[i] > h[k]) k = i;
        return s.substr(sa[k], h[k]);
    }
    
private:
    static const int N = 3e4 + 10;
    int wa[N], wb[N], ws[N], wv[N], sa[N], ra[N], h[N];
    
    inline bool cmp(int *r, int a, int b, int len, int n) {
        if (r[a] != r[b]) return false;
        a = (a + len < n ? r[a + len] : -1);
        b = (b + len < n ? r[b + len] : -1);
        return a == b;
    }
    
    void SA(string s) {
        int n = s.size(), m = 128;
        int i, j, p, *x = wa, *y = wb, *t;
        for (i = 0; i < m; i++) ws[i] = 0;
        for (int i = 0; i < n; i++) ws[x[i] = s[i]]++;
        for (int i = 1; i < m; i++) ws[i] += ws[i - 1];
        for (int i = n - 1 ; i >= 0; i--) sa[--ws[x[i]]] = i;
        
        for (j = p = 1; p < n; j <<= 1, 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 < m; i++) ws[i] = 0;
            for (i = 0; i < n; i++) ws[wv[i] = x[y[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 (t = x, x = y, y = t, x[sa[0]] = 0, i = p = 1; i < n; i++)
                x[sa[i]] = (cmp(y, sa[i - 1], sa[i], j, n) ? p - 1 : p++);
        }
     
        
        for (i = 0; i < n; i++) ra[sa[i]] = i; // 获取 ra 数组
        int k;
        for (i = 0, k = 0; i < n; i++) {
            if (ra[i] == 0) continue;
            if (k) k--;
            while (s[i + k] == s[sa[ra[i] - 1] + k]) k++;
            h[ra[i]] = 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
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

是否有某字符串在文本串中至少不重叠地出现了两次

可以二分目标串的长度 |s|，将 lcp 数组划分成若干个连续 LCP 大于等于 |s| 的段，利用 RMQ 对每个段求其中出现的数中最大和最小的下标，若这两个下标的距离满足条件，则一定有长度为 |s| 的字符串不重叠地出现了两次。