E2. Erase and Extend (Hard Version) - 题解

比赛与标签

比赛: Codeforces Round 726 (Div. 2) 标签: binary search, data structures, greedy, hashing, string suffix structures, strings, two pointers 难度: *2200

题目大意喵~

主人你好呀~！这道题是说，我们有一个初始字符串 s，还有两个神奇的魔法可以用喵：

删除术: 可以删掉字符串的最后一个字符。
复制术: 可以把整个字符串复制一遍，接到自己的尾巴上（s := s + s）。

我们的任务是，通过任意次使用这两个魔法，最后得到一个长度正好是 k 的、字典序最小的字符串。字典序最小，就是说在字母表里尽可能靠前啦，比如 "a" 就比 "b" 小，"cat" 就比 "dog" 小，喵~

输入会给我们初始字符串的长度 n、目标长度 k 和字符串 s 本身。我们要输出那个最终的、最完美的、长度为 k 的字符串！

本喵的解题思路！

哼哼，这道题看起来花里胡哨的，但本喵一眼就看穿了它的本质，喵呜~

我们来分析一下这两个操作能做什么吧。

删除术 让我们能得到 s 的任意一个前缀。比如说 s = "abcde"，我们可以通过删除操作得到 "abcd", "abc", "ab", "a"。
复制术 让我们能把当前得到的字符串无限地重复下去。比如我们得到了前缀 "ab"，用复制术就会变成 "abab", "abababab"...

所以，整个操作流程其实可以简化成三步：

首先，用删除术从原字符串 s 中选一个心仪的前缀，我们叫它 p 好了。
然后，用复制术把这个前缀 p 无限地重复，形成一个无限长的字符串 p + p + p + ...
最后，从这个无限长的字符串里，取出前 k 个字符，就是我们的最终答案啦！

那么问题就变成了：我们应该选择 s 的哪个前缀 p，才能让它无限重复后形成的字符串字典序最小呢？

这是一个很经典的贪心问题哦！我们可以用一个指针从左到右扫描字符串 s，同时维护一个当前找到的“最优前缀”的长度，我们叫它 best_len。

一开始，最简单的前缀就是第一个字符 s[0]，所以我们假设 best_len = 1。
然后我们从第二个字符 s[1] 开始往后看，对于每个位置 i，我们都在考虑要不要把 s[0...i] 这个新前缀作为我们新的“最优前缀”。
怎么判断 s[0...i] 是不是比当前最优的前缀 s[0...best_len-1] 更好呢？我们需要比较它们无限重复后的结果。其实我们不需要真的去比较无限长的字符串，有一个很巧妙的方法呐！
- 我们只需要比较 s[i] 和 s[i % best_len] 这两个字符。s[i % best_len] 正是当前最优前缀 s[0...best_len-1] 无限重复后，在第 i 个位置（0-indexed）上会出现的字符。
- 情况一：s[i] < s[i % best_len] 太棒了喵！这意味着新前缀 s[0...i] 在第 i 位上出现了一个更小的字符。那么它生成的无限字符串一定比之前的好！所以我们立刻更新 best_len = i + 1，把它作为我们新的最优选择。
- 情况二：s[i] > s[i % best_len] 呜哇，不妙！新前缀 s[0...i] 在第 i 位上出现了一个更大的字符。这意味着它已经输了。并且，任何以 s[0...i] 开头的前缀（比如 s[0...i+1] 等）也肯定会输。所以我们没有必要再往后看了，可以直接 break 循环，当前的 best_len 就是最终的答案。
- 情况三：s[i] == s[i % best_len] 嗯...这两个前缀在第 i 位上还是一样的。我们暂时还分不出胜负，所以什么都不做，继续往后比较，看看下一个字符会不会带来转机。我们不更新 best_len，因为在结果相同的情况下，我们更喜欢短一点的前缀，这样更灵活嘛。

通过这样一次遍历，我们就能找到那个能产生字典序最小无限字符串的最优前缀长度 best_len。

最后一步，就是用这个最优前缀 s[0...best_len-1] 来构造长度为 k 的答案。我们只需要不断地重复这个前缀，输出 k 个字符就好啦。第 j 个字符就是 s[j % best_len]。

代码实现的说

cpp

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

// 这就是解决问题的函数喵~
void solve() {
    int n, k;
    std::cin >> n >> k;
    std::string s;
    std::cin >> s;

    // 问题的本质是找到 s 的一个前缀，这个前缀无限重复后形成的字符串字典序最小。
    // 任何操作序列都可以等价于：
    // 1. 选择 s 的一个前缀 (通过删除末尾字符)。
    // 2. 无限重复这个前缀 (通过复制操作)。
    // 3. 取前 k 个字符作为结果。
    //
    // 所以，我们只需要找到最优的那个前缀 s[0...i-1] 就行啦。
    // 我们可以通过一次遍历找到这个最优前缀的长度。

    // best_len 记录了目前找到的最优前缀的长度。
    // 一开始，我们认为长度为 1 的前缀 s[0] 是最好的候选者。
    int best_len = 1;

    // 我们遍历所有可能的前缀长度，从 2 到 n。
    // 循环变量 i 是我们正在考虑的前缀的最后一个字符的索引（0-based）。
    // 这个前缀的长度就是 i + 1。
    for (int i = 1; i < n; ++i) {
        // current_char 是我们正在考虑加入前缀的新字符。
        char current_char = s[i];
        
        // 要判断新前缀 s[0...i] 是否比当前最优前缀 s[0...best_len-1] 更好，
        // 我们需要比较它们无限重复后的结果。
        // 这个比较可以逐字符进行。我们的算法保证了 s[0...i-1] 是 s[0...best_len-1] 无限重复串的前缀。
        // 所以，第一个可能出现差异的地方就在索引 i。
        // 我们将 s[i] 与最优前缀无限重复后在位置 i 的字符进行比较。
        // 这个字符就是 s[i % best_len]。
        char best_prefix_char = s[i % best_len];

        if (current_char < best_prefix_char) {
            // 如果 s[i] 更小，说明新前缀 s[0...i] 更好！
            // 它的无限重复串字典序会更小。
            // 所以，我们更新最优前缀的长度。
            best_len = i + 1;
        } else if (current_char > best_prefix_char) {
            // 如果 s[i] 更大，说明新前缀 s[0...i] 更差。
            // 任何以 s[0...i] 开头的更长的前缀也都会更差。
            // 因此，我们可以停止寻找更好的前缀了。
            break;
        }
        // 如果 current_char == best_prefix_char，说明前缀 s[0...i] 并不严格更优。
        // 我们可以证明，如果 u 是 v^inf 的前缀，那么 u^inf >= v^inf。
        // 所以我们不更新 best_len，继续寻找下一个字符。
    }

    // 找到最优前缀长度 best_len 后，我们通过重复这个前缀 s[0...best_len-1]
    // 来构造长度为 k 的结果字符串。
    for (int i = 0; i < k; ++i) {
        std::cout << s[i % best_len];
    }
    std::cout << '\n';
}

int main() {
    // 加速一下 I/O，跑得更快，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    solve();

    return 0;
}

爪爪的复杂度分析

时间复杂度: O(n + k) 的说。我们有一个循环来寻找 best_len，这个循环最多执行 n-1 次，所以是 O(n)。之后，我们还有一个循环来输出 k 个字符，这是 O(k)。加起来，总的时间复杂度就是 O(n + k) 啦，非常高效！
空间复杂度: O(n) 的说。我们主要需要空间来存储输入的字符串 s，长度为 n。因为我们是直接输出字符，没有额外构建一个长度为 k 的字符串，所以除了输入占用的空间外，额外空间是 O(1) 的。总的空间复杂度就是 O(n) 啦。

知识点小鱼干~

这道题真有趣，让本喵总结一下学到的小知识吧！

问题转化: 解决复杂问题的关键一步，往往是把它转化成一个我们更熟悉、更简单的模型。这道题里，看似复杂的操作被我们转化为了“寻找最优重复前缀”的问题，思路一下子就清晰了！
贪心算法: 我们的解法是一个非常漂亮的贪心策略。每一步都做出当前看起来最好的选择（找到一个能让字典序变小的新字符），最终得到了全局最优解。break 的运用更是贪心思想的体现，一旦发现当前路径已经不是最优，就果断放弃，避免了不必要的计算。
字符串的周期性: s[i % best_len] 这个技巧，是处理字符串重复/周期性问题的利器！它让我们能用 O(1) 的时间复杂度，查询到一个无限重复字符串在任意位置的字符，非常巧妙，主人一定要记住哦！
边界与细节: 在比较时，只有当新字符 strictly smaller（严格小）时才更新 best_len。这保证了在生成相同无限串的情况下（例如 "a" 和 "aa"），我们会选择更短的那个前缀，这是符合贪心直觉的。

希望本喵的题解能帮到你哦！继续加油，算法的世界还有好多有趣的宝藏等着我们去发现呢，喵~！

E2. Erase and Extend (Hard Version) - 题解 ​

比赛与标签 ​

题目大意喵~ ​

本喵的解题思路！ ​

代码实现的说 ​

爪爪的复杂度分析 ​

知识点小鱼干~ ​