后缀数组

· · 算法·理论

定义

全文使用 1-index。

对于字符串 S,定义 \text{sa}[i] 为将 S 排序后第 i 小后缀的标号,\text{rk}[i] 为标号为 i 的后缀排序。根据定义,\text{sa} 和 \text{rk} 互为逆排列。

记 \text{lcp}(i,j) 为 S[i:n] 和 S[j:n] 的 LCP 长度,设 \text{ht}[i]=\text{lcp}(\text{sa}[i-1],\text{sa}[i])。

求法

哈希

初始化 \text{sa} 为单位排列,对其进行排序。每轮 cmp 只要比较两个后缀的字典序,二分哈希求 LCP 长后比较下一位即可。

复杂度为 O(n \log^2 n)。建议使用倍增求 LCP 配合 std::stable_sort。

倍增

考虑在第 k 轮排序中只比较 S[i:i+2^k-1] 的字典序。

在第 k+1 轮中,我们需要对 (S[i:i+2^k-1], S[i+2^k:i+2^{k+1}-1]) 的二元组排序。这两个东西在上一轮都排好了,所以可以直接 std::sort。复杂度 O(n \log^2 n)。

由于值域是 O(n) 的,可以用计数排序来优化。对于双关键字排序,还要采用基数排序的思想,先对第二关键字排序,再对第一关键字排序。复杂度 O(n \log n)。

常数优化:第二关键字排序可以直接模拟;限制值域。

板子

倍增实现的单 \log 做法。

struct suffix_array {
    int sa[2 * N], rk[2 * N], ht[N], rk0[N], cnt[N], id[N];
    void init(const char* s, int n, int m = 130) {
        for (int i = 1; i <= n; i++) cnt[rk[i] = s[i]]++;
        for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i;
        for (int k = 1, p = 0; p < n; k <<= 1, m = p) {
            int cur = 0;
            for (int i = n-k+1; i <= n; i++) id[++cur] = i;
            for (int i = 1; i <= n; i++) if (sa[i] > k) id[++cur] = sa[i] - k;
            fill(cnt + 1, cnt + m + 1, 0);
            for (int i = 1; i <= n; i++) cnt[rk[id[i]]]++;
            for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
            for (int i = n; i >= 1; i--) sa[cnt[rk[id[i]]]--] = id[i];
            p = 0, copy(rk + 1, rk + n + 1, rk0 + 1);
            auto equ = [&](int x, int y) -> bool {
                return rk0[x] == rk0[y] && rk0[x + k] == rk0[y + k];
            };
            for (int i = 1; i <= n; i++) rk[sa[i]] = equ(sa[i - 1], sa[i]) ? p : ++p;
        }
        for (int i = 1, j = 0; i <= n; i++) {
            if (rk[i] == 0) continue;
            for (j ? j-- : 0; s[i+j] == s[sa[rk[i]-1] + j]; ) j++;
            ht[rk[i]] = j;
        }
    }
} SA;

结论

练习

P4248 [AHOI2013] 差异

给出长为 n 的字符串 S,记 T_i=S[i:n],求

\sum_{1 \le i< j \le n} (|T_i|+|T_j|-2 \times \text{lcp}(T_i,T_j))

:::::success[题解]

前面 \sum\limits_{1 \le i<j \le n} (|T_i|+|T_j|) 容易推式子变成 \frac{n(n-1)(n+1)}{2} 从而 O(1) 计算。

求出 \text{ht} 数组后,相当于我们要对区间 \min 求和。这是 AGC005B,做法是单调栈求出以 \text{ht}[x] 为 \min 的极长区间,算一下贡献。

注意单调栈一侧取等一侧不取的细节。

:::::

:::::info[代码]

void _main() {
    cin >> (s + 1); n = strlen(s + 1);
    SA.init(s, n);
    i64 res = 1LL * (n - 1) * n * (n + 1) / 2;
    stack<int> st;
    for (int i = 2; i <= n; i++) {
        while (!st.empty() && SA.ht[st.top()] > SA.ht[i]) st.pop();
        l[i] = st.empty() ? 2 : st.top() + 1; st.emplace(i);
    }
    while (!st.empty()) st.pop();
    for (int i = n; i >= 2; i--) {
        while (!st.empty() && SA.ht[st.top()] >= SA.ht[i]) st.pop();
        r[i] = st.empty() ? n : st.top() - 1; st.emplace(i);
    }
    for (int i = 2; i <= n; i++) 
        res -= 2LL * (i - l[i] + 1) * (r[i] - i + 1) * SA.ht[i];
    cout << res;
}

:::::

P6640 [BJOI2020] 封印

给定字符串 S,T,字符集为 \{\tt{a},\tt{b}\}。q 次询问给定 l,r,求 S[l:r] 与 T 的最长公共子串长度。

:::::success[题解]

钦定 i 为 S 中子串的起始位置,求出最长公共子串长度,记为 f_i。枚举最长公共子串的起点 i,则询问 [l,r] 的答案为

\max_{i \in [l,r]} \min(f_i,r-i+1)

二分答案 k,则 \exists i \in [l,r], \min(f_i,r-i+1) \ge k。拆开不等式得 f_i \ge k \land r-i+1 \ge k,转化为 \max\limits_{i \in [l,r-k+1]} f_i \ge k。用 ST 表维护,复杂度 1log。

::::: :::::info[代码] ```cpp line-numbers const int N = 4e5 + 5, inf = 1e9; int n, m, q, f[N], st[20][N]; string s, t; int ask(int l, int r) { int k = lg(r - l + 1); return max(st[k][l], st[k][r - (1 << k) + 1]); } void _main() { cin >> s >> t; n = s.size(); string a = ' ' + s + '#' + t; m = a.size() - 1, SA.init(a.c_str(), m); for (int i = 1, k = 0; i <= m; i++) { chkmin(k, SA.ht[i]); if (SA.sa[i] > n + 1) k = inf; if (SA.sa[i] <= n) chkmax(f[SA.sa[i]], k); } for (int i = m, k = 0; i >= 1; i--) { if (SA.sa[i] > n + 1) k = inf; if (SA.sa[i] <= n) chkmax(f[SA.sa[i]], k); chkmin(k, SA.ht[i]); } copy(f + 1, f + n + 1, st[0] + 1); for (int i = 1; (1 << i) <= n; i++) for (int j = 1; j + (1 << i) - 1 <= n; j++) st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]); cin >> q; for (int l, r; q--; ) { cin >> l >> r; int lo = 1, hi = r - l + 1, res = 0; while (lo <= hi) { int k = (lo + hi) >> 1; if (ask(l, r - k + 1) >= k) res = k, lo = k + 1; else hi = k - 1; } cout << res << '\n'; } } ``` ::::: ### [P4770 [NOI2018] 你的名字](https://www.luogu.com.cn/problem/P4770) > 给定字符串 $S$,$q$ 次询问给出 $l,r,T$,求 $T$ 中不在 $S[l:r]$ 内出现的本质不同子串数。 > > $|S| \le 5 \times 10^5$,$q \le 10^5$,$\sum |T| \le 10^6$,5 秒,1024 MB。 ### [P6793 [SNOI2020] 字符串](https://www.luogu.com.cn/problem/P6793) > 给定两个长为 $n$ 的字符串 $A,B$ 和正整数 $k$。各自取出所有长为 $k$ 的子串组成集合 $S,T$。 > > 你需要将 $S$ 和 $T$ 中的元素两两匹配,匹配 $s,t$ 的代价为 $k-\text{lcp}(s,t)$。最小化代价并输出。 > > $k \le n \le 1.5 \times 10^5$,1 秒,256 MB。 :::::success[题解] 不妨视匹配 $s,t$ 的权值为 $\text{lcp}(s,t)$,转为最大权完美匹配。 对 $A{\tt{\#}}B$ 后缀排序得到 $\text{ht}$ 数组,权值可以描述为 $\text{ht}$ 数组的区间 $\min$。由于区间 $\min$ 满足四边形不等式,或者说相交劣于包含的性质,我们可以直接贪心匹配权值最小的边。 考虑维护贪心过程。对 $\text{ht}$ 建小根笛卡尔树,自底向上贪心。对节点 $u$,我们维护失配的 $s,t$ 数目 $x,y$,并在 $u$ 处尽可能匹配。 形式化地,我们求出 $q=\min(x,y)$,对答案累加 $q \times \min(k,\text{ht}[u])$ 后,将 $x \gets x-q, y \gets y-q$ 传递给父亲进行匹配即可。 线性 SA 可以做到总复杂度线性。 ::::: :::::info[代码] ```cpp line-numbers const int N = 3e5 + 5; int n, k, m, l[N], r[N]; string a, b; int build(int* a) { int rt = -1; stack<int> st; for (int i = 2; i <= m; i++) { while (!st.empty() && a[st.top()] > a[i]) l[i] = st.top(), st.pop(); st.empty() ? (rt = i) : (r[st.top()] = i), st.emplace(i); } return rt; } i64 ans; pair<int, int> dfs(int u) { int x = 0, y = 0; if (l[u]) { auto [x0, y0] = dfs(l[u]); x += x0, y += y0; } else { int v = SA.sa[u-1]; x += (v <= n-k+1), y += (n+2 <= v && v <= 2*n-k+2); } if (r[u]) { auto [x0, y0] = dfs(r[u]); x += x0, y += y0; } else { int v = SA.sa[u]; x += (v <= n-k+1), y += (n+2 <= v && v <= 2*n-k+2); } i64 q = min(x, y); ans += q * min(k, SA.ht[u]); return {x - q, y - q}; } void _main() { cin >> n >> k >> a >> b; string c = ' ' + a + '#' + b; m = c.size() - 1, SA.init(c.c_str(), m); int rt = build(SA.ht); dfs(rt); cout << 1LL * k * (n - k + 1) - ans; } ``` :::::