B-SuffixArray - 题解

标签与难度

标签: 字符串, 后缀数组, 排序, 倍增法, 构造难度: 2300

题目大意喵~

主人你好呀~ 这道题是关于一个叫做 B-function 的奇妙变换的，喵！

给定一个只包含 'a' 和 'b' 的字符串 s，长度为 n。对于任意一个字符串 t，它的 B-function B(t) 是一个整数序列。B(t) 的第 i 个元素 b_i 的计算规则是：

如果在 t 中，t_i 这个字符在它前面出现过（即存在 j < i 使得 t_j = t_i），那么 b_i 就是 t_i 与它前面最近的那个相同字符的距离 i - j。
如果 t_i 在它前面没有出现过，那么 b_i 就等于 0。

我们的任务是，对原字符串 s 的所有 n 个后缀（从 s[1..n], s[2..n], ..., s[n..n]），分别计算出它们的 B-function，然后根据这些 B-function 的字典序，对这 n 个后缀进行升序排序。最后，输出排序后后缀的起始下标 p_1, p_2, ..., p_n。

举个栗子，如果 s = "ababa":

后缀 "aba" 的 B-function 是 [0, 0, 2]。
后缀 "baba" 的 B-function 是 [0, 0, 2, 2]。因为 [0, 0, 2] 在字典序上小于 [0, 0, 2, 2]，所以后缀 "aba" 要排在 "baba" 的前面哦，喵~

解题思路分析

这道题的核心是比较两个后缀的 B-function 的字典序。直接为每个后缀生成完整的 B-function 再排序，长度最长可达 $O(N)$ ，总共有 $N$ 个后缀，时间和空间复杂度都会是 $O(N^2)$ ，对于 $N=10^5$ 的数据量来说，肯定会超时的说！我的爪子可受不了这么大的计算量，必须想个更聪明的办法，喵！

我们的目标是找到一个高效的比较方法 compare(i, j)，用来判断后缀 s[i..n] 和 s[j..n] 对应的 B-function 哪个更小。

关键洞察：B-function 的结构

让我们来挠一挠这个 B-function，看看它有什么结构特点。考虑一个后缀 t = s[i..n]，它只包含 'a' 和 'b' 两种字符。

假设 s[i] = 'a'。这个后缀会以一串 'a' 开始，直到遇到第一个 'b'，或者直到字符串末尾。
设第一个 'b' 出现在位置 p（如果不存在，就当 p=n+1）。
那么，s[i..p-1] 全是 'a'。这部分对应的 B-function 是什么样呢？
- s[i] 是第一个 'a'，B-value 是 0。
- s[i+1] 是 'a'，前一个 'a' 在 s[i]，距离是 1。
- s[i+2] 是 'a'，前一个 'a' 在 s[i+1]，距离是 1。
- ...
- 所以，s[i..p-1] 对应的 B-function 前缀是 [0, 1, 1, ..., 1]，长度为 p-i。
接下来是 s[p]，这是后缀 t 中出现的第一个 'b'。根据定义，它的 B-value 是 0。
综上，B(t) 的开头部分是 [0, 1, ..., 1, 0, ...]，其中 1 有 p-i-1 个。

这个发现太棒啦！我们可以根据这个结构来比较两个后缀 s[i..n] 和 s[j..n]。

令 p_i 为后缀 s[i..n] 中第一个不同于 s[i] 的字符的位置，p_j 为后缀 s[j..n] 中第一个不同于 s[j] 的字符的位置。
初始相同字符块的长度分别为 len_i = p_i - i 和 len_j = p_j - j。
如果 len_i < len_j，那么 B(s[i..n]) 在第 len_i + 1 位是 0，而 B(s[j..n]) 在这一位是 1。因此 B(s[i..n]) 字典序更小！
如果 len_i > len_j，同理，B(s[j..n]) 字典序更小。

当初始块长度相同时

最有趣的部分来啦！如果 len_i = len_j，说明它们 B-function 的前 len_i + 1 位都是 [0, 1, ..., 1, 0]，完全一样。我们需要比较后面的部分。

后面的部分是 B(s[i..n]) 从第 len_i+2 位开始，和 B(s[j..n]) 从第 len_j+2 位开始的比较。这相当于比较从 s[p_i+1] 和 s[p_j+1] 开始的 "子问题"。

我们来研究一下 B(s[i..n]) 在 k > p_i - i + 1 处的 k-th value。这个值对应于原串中 s_{i+k-1} 这个字符。它的 B-value 是 (i+k-1) - q，其中 q 是 s_{i+k-1} 在 s[i..i+k-2] 中最后出现的位置。

我们来定义一个辅助数组 b_val。b_val[k] 表示字符 s_k 与它在整个字符串 s 中前一个相同字符的距离。如果 s_k 是第一次出现，b_val[k] = 0。这个数组可以在 $O(N)$ 时间内预处理出来。例如 s = "ababa"，b_val = [0, 0, 2, 2, 2]。

现在，奇迹发生了！对于 k > p_i，我们来计算 s_k 在后缀 s[i..n] 中的 B-value。

s_k 的前一个相同字符的位置，设为 q_full (在整个串中) 和 q_suffix (在后缀 s[i..]中)。
b_val[k] = k - q_full。
s_k 在后缀 s[i..] 中的 B-value 是 k - q_suffix。
我们需要证明 q_full = q_suffix，也就是说 q_full >= i。
因为 k > p_i，而 p_i 是第一个和 s_i 不同的字符的位置。
- 如果 s_k 和 s_i 相同，那它在 s[i..p_i-1] 中肯定出现过，所以 q_full >= i。
- 如果 s_k 和 s_i 不同，那它和 s_{p_i} 相同。它在 s[p_i..k-1] 中肯定出现过（或它就是s_{p_i}），所以 q_full >= p_i >= i。
结论：对于 k > p_i，s_k 在后缀 s[i..n] 中的 B-value 就等于 b_val[k]！

喵嗷！这意味着，当 len_i = len_j 时，比较 B(s[i..n]) 和 B(s[j..n]) 的后半部分，等价于比较两个 b_val 数组的后缀：b_val[p_i+1..n] 和 b_val[p_j+1..n] 的字典序！

最终算法

这下思路就清晰了，像猫咪找到了毛线球一样！

预处理 b_val 数组: $O(N)$ 时间。遍历字符串 s，用一个数组记录 'a' 和 'b' 最后出现的位置，计算出 b_val。
预处理 b_val 的后缀序: 对 b_val 这个整数序列，构建后缀数组。我们可以用倍增法在 $O(N \log N)$ 时间内求出 sa 和 rk 数组。rk[k] 就是 b_val 中后缀 b_val[k..n] 的排名。
构造排序元信息: 对于每个后缀起始位置 i = 0..n-1，我们构造一个元组 (len_mono, rank_of_tail, original_index) 用于排序。
- original_index = i。
- len_mono 是 s[i..n] 的初始同色块长度。这可以 $O(N)$ 预计算出每个位置之后下一个 'a' 和 'b' 的位置来得到。
- rank_of_tail 是 b_val 对应部分的排名。如果初始块后还有字符（即 p_i <= n），则 rank_of_tail = rk[p_i + 1]。如果到结尾都是同色，可以设为一个特殊值（比如 -1）。
排序: 对所有后缀的元信息元组进行排序。排序规则是：优先比较 len_mono，小的在前；若相等，则比较 rank_of_tail，小的在前。
输出结果: 输出排序后元组中的 original_index 即可。

整个算法的瓶颈在于后缀数组的构建，所以总时间复杂度是 $O(N \log N)$ ，空间复杂度是 $O(N)$ 。完美解决问题，喵~

代码实现

这是我根据上面的思路，精心重构的一份代码，加满了注释，希望能帮到你哦！

cpp

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

// 使用一个命名空间来封装后缀数组的逻辑，代码更整洁喵~
namespace SuffixArray {
    std::vector<int> sa, rk;

    // 倍增法构建后缀数组 (SA-IS 也可以，但倍增法更经典)
    void build(int n, const std::vector<int>& s, int m) {
        sa.resize(n + 1);
        rk.resize(n + 1);
        std::vector<int> old_rk(n + 1, 0);
        std::vector<int> cnt(m + 1, 0);
        std::vector<int> y(n + 1, 0);

        // 初始排序 (k=1)
        for (int i = 1; i <= n; ++i) {
            rk[i] = s[i - 1]; // s是0-indexed, rk/sa是1-indexed
            cnt[rk[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; k < n; k <<= 1) {
            int p = 0;
            // 第二关键字排序
            for (int i = n - k + 1; i <= n; ++i) y[++p] = i;
            for (int i = 1; i <= n; ++i) {
                if (sa[i] > k) y[++p] = sa[i] - k;
            }
            // 第一关键字排序
            std::fill(cnt.begin(), cnt.end(), 0);
            for (int i = 1; i <= n; ++i) cnt[rk[i]]++;
            for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
            for (int i = n; i >= 1; --i) sa[cnt[rk[y[i]]]--] = y[i];

            // 更新rk
            std::copy(rk.begin(), rk.end(), old_rk.begin());
            p = 0;
            for (int i = 1; i <= n; ++i) {
                if (old_rk[sa[i]] == old_rk[sa[i - 1]] &&
                    (sa[i] + k <= n ? old_rk[sa[i] + k] : -1) == (sa[i-1] + k <= n ? old_rk[sa[i-1] + k] : -1)) {
                    rk[sa[i]] = p;
                } else {
                    rk[sa[i]] = ++p;
                }
            }
            m = p;
            if (p == n) break;
        }
    }
}

// 用于排序的元信息结构体
struct SuffixInfo {
    int id;              // 后缀的起始下标 (0-indexed)
    int mono_block_len;  // 初始同色块的长度
    int tail_rank;       // 尾部在b_val后缀数组中的排名

    bool operator<(const SuffixInfo& other) const {
        if (mono_block_len != other.mono_block_len) {
            return mono_block_len < other.mono_block_len;
        }
        return tail_rank < other.tail_rank;
    }
};

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::string s;
    while (std::cin >> n >> s) {
        // 1. 预处理 b_val 数组
        std::vector<int> b_val(n);
        int last_pos_a = -1, last_pos_b = -1;
        for (int i = 0; i < n; ++i) {
            if (s[i] == 'a') {
                b_val[i] = (last_pos_a == -1) ? 0 : i - last_pos_a;
                last_pos_a = i;
            } else {
                b_val[i] = (last_pos_b == -1) ? 0 : i - last_pos_b;
                last_pos_b = i;
            }
        }

        // 2. 构建 b_val 的后缀数组
        // 为了处理 b_val[p_i+1] 的情况，我们需要一个空后缀，所以多加一个元素
        std::vector<int> b_val_extended = b_val;
        b_val_extended.push_back(-1); // 加上一个最小的字符，代表结尾
        // 将 b_val 的值离散化到从1开始的整数，方便SA处理
        std::vector<int> temp_sorted = b_val_extended;
        std::sort(temp_sorted.begin(), temp_sorted.end());
        temp_sorted.erase(std::unique(temp_sorted.begin(), temp_sorted.end()), temp_sorted.end());
        
        std::vector<int> discrete_b_val(n + 1);
        for(int i = 0; i <= n; ++i) {
            discrete_b_val[i] = std::lower_bound(temp_sorted.begin(), temp_sorted.end(), b_val_extended[i]) - temp_sorted.begin() + 1;
        }

        SuffixArray::build(n + 1, discrete_b_val, temp_sorted.size());

        // 3. 构造排序元信息
        std::vector<int> next_a(n + 1, n), next_b(n + 1, n);
        for (int i = n - 1; i >= 0; --i) {
            next_a[i] = next_a[i + 1];
            next_b[i] = next_b[i + 1];
            if (s[i] == 'a') next_a[i] = i;
            else next_b[i] = i;
        }

        std::vector<SuffixInfo> infos;
        for (int i = 0; i < n; ++i) {
            int first_other_pos = (s[i] == 'a') ? next_b[i] : next_a[i];
            int mono_len = first_other_pos - i;
            int tail_rk = SuffixArray::rk[first_other_pos + 1 + 1]; // b_val[p+1]对应discrete_b_val[p+1], sa是1-indexed
            infos.push_back({i, mono_len, tail_rk});
        }

        // 4. 排序
        std::sort(infos.begin(), infos.end());

        // 5. 输出结果
        for (int i = 0; i < n; ++i) {
            std::cout << infos[i].id + 1 << (i == n - 1 ? "" : " ");
        }
        std::cout << "\n";
    }

    return 0;
}

注意: 上面的代码中，为了处理 b_val[p+1] 的后缀排名，我对 b_val 数组进行了一点扩展和离散化。当 p=n 时，p+1 就超出了原数组范围，所以扩展一位并用一个最小的字符填充，这样 rk[n+1] 就会是最小的，逻辑就统一了。SA的 rk 和 sa 数组通常是1-indexed的，所以在使用时要注意下标转换，喵~

复杂度分析

时间复杂度: $O(N \log N)$
- 预处理 b_val 数组和 next_a/next_b 数组都是 $O(N)$ 。
- b_val 的离散化是 $O(N \log N)$ （因为排序）。
- 构建后缀数组是 $O((N+1) \log(N+1))$ ，也就是 $O(N \log N)$ 。
- 构造 SuffixInfo 向量是 $O(N)$ 。
- 对 SuffixInfo 向量排序是 $O(N \log N)$ 。
- 所以总的时间复杂度由后缀数组构建和排序主导，为 $O(N \log N)$ 。
空间复杂度: $O(N)$
- s, b_val, next_a, next_b 等数组都是 $O(N)$ 。
- 后缀数组算法本身需要多个辅助数组，也都是 $O(N)$ 。
- SuffixInfo 向量是 $O(N)$ 。
- 总的空间复杂度是 $O(N)$ 。

知识点总结

这道题真是一次有趣的冒险，喵！我们用到的知识点有：

问题分解与转化: 最核心的技巧！把一个复杂的比较问题（比较B-function）分解成更简单的元组 (len_mono, rank_of_tail) 的比较。这是解决困难问题的常用策略。
后缀数组 (Suffix Array): 这是解决字符串后缀相关问题的强大工具。这道题展示了后缀数组不仅能用于字符串，还能用于任何整数序列，来解决后缀的字典序比较问题。
倍增法 (Doubling Algorithm): 构建后缀数组的经典算法之一，通过每次将排序的子串长度加倍，逐步得到最终的后缀排序。
预处理思想: 通过 $O(N)$ 的预处理（如 b_val, next_a, next_b），为后续的 $O(1)$ 查询或构造提供便利，大大优化了整体效率。

希望这篇题解能帮助你更好地理解这道题！如果还有问题，随时可以再来问我哦，喵~

B-SuffixArray - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

关键洞察：B-function 的结构 ​

当初始块长度相同时 ​

最终算法 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​