E. Nearly Shortest Repeating Substring - 题解

比赛与标签

比赛: Codeforces Round 937 (Div. 4) 标签: brute force, implementation, number theory, strings 难度: *1500

题目大意喵~

你好呀，未来的算法大师！今天我们来解决一个非常有趣的字符串问题，喵~

题目是这样子的：给你一个长度为 n 的字符串 s。你需要找到一个最短的字符串 k，用它自己重复拼接若干次（比如 x 次），可以得到一个新字符串 c。这个新字符串 c 必须和我们原来的 s 长度相同，并且 c 和 s 最多只能有一个位置的字符不一样。

举个栗子呐： 如果 s = "abaa"，长度 n=4。 我们可以选 k = "a"，它的长度是 1。 用 k 重复4次得到 c = "aaaa"。 比较 s = "abaa" 和 c = "aaaa"，只有第二个位置的 'b' 和 'a' 不同，只有一个差异！ 因为长度1是最小的可能性，所以答案就是1，是不是很简单呢？

我们的任务就是找出这个最短的 k 的长度 L。

解题思路大揭秘！

初看这道题，可能会觉得有点无从下手，要去哪里找那个神秘的字符串 k 呢？别急，让本猫娘带你一步步拆解这个问题，你会发现它其实有很清晰的脉络哦！

关键线索：周期的长度一定是 n 的约数！

这是解开谜题的第一把钥匙，也是最重要的一个性质！ 如果字符串 k 的长度是 L，它重复 x 次构成了长度为 n 的字符串 c，那么必然有 L * x = n。这说明什么？说明 L 必须是 n 的一个约数（也叫因数）！

哇！这个发现太棒了！我们不需要从 1 到 n 检查所有可能的长度了，只需要检查 n 的所有约数就好。对于一个 n 来说，它的约数个数可比 n 本身小得多得多，这大大缩小了我们的搜索范围。

为了找到最短的 k，我们只需要按从小到大的顺序检查 n 的每一个约数 L，第一个满足条件的 L 就是我们的答案！

如何验证一个长度 L 是否可行？

好，现在我们有了一个候选的长度 L（它是 n 的一个约数）。接下来要怎么验证它呢？我们需要构造出那个完美的周期字符串 c，然后和 s 比较。

那么，这个 k 到底是什么样的呢？ 想一想，c 和 s 最多只有一个字符不同。这意味着 s 本身也必须是几乎周期性的。如果我们把 s 切成 n/L 个长度为 L 的小块，这些小块应该几乎一模一样。

这个 "最多一个不同" 的差异，可能出现在 s 的任何位置。

• 情况一：没有差异。 s 本身就是一个完美的周期字符串。那么它的第一个长度为 L 的前缀 s[0...L-1] 就是我们的 k。
• 情况二：有一个差异。 这个差异只会影响到 s 的某一个长度为 L 的块。这意味着，s 的其他所有块都是完全相同的，并且它们就是真正的 k 的样子！

那么，我们怎么能稳定地找到这个真正的 k 呢？ 一个非常聪明的策略是：我们不需要去大海捞针！我们可以从 s 自身中提取候选的 k。 因为绝大多数块都是正确的 k，所以我们可以尝试用 s 的第一个块（即前缀 s[0...L-1]）作为 k 来生成 c，然后检查它和 s 的差异。

但是，万一那个唯一的错误恰好就在第一个块里怎么办？ 比如 s = "xbcdabcdabcd"，n=12, L=4。 如果用第一个块 k="xbcd" 生成 c，会得到 "xbcdxbcdxbcd"，和 s 有两个差异。 但真正的 k 其实是 "abcd"，生成的 c 是 "abcdabcdabcd"，和 s 只有一个差异。

为了解决这个问题，我们可以多找一个候选者！除了第一个块，我们再试试最后一个块（即后缀 s[n-L...n-1]）。 只要 n/L >= 2（也就是说至少有两个块），那个唯一的错误就不可能同时污染第一个块和最后一个块。所以，这两个候选者中至少有一个是正确的 k！

所以，我们的完整策略来啦：

1. 找出 n 的所有约数。
2. 将这些约数从小到大排序。
3. 遍历每一个约数 L： a. 候选一：假设 k 是 s 的前缀 s[0...L-1]。用它生成周期串 c1，然后检查 c1 和 s 的差异数是否 ≤ 1。如果是，那么 L 就是答案，直接输出并结束！ b. 候选二：如果候选一失败了，再假设 k 是 s 的后缀 s[n-L...n-1]。用它生成周期串 c2，检查差异数是否 ≤ 1。如果是，L 也是答案，输出并结束！
4. 因为我们是从小到大检查 L 的，所以第一个找到的答案一定是最小的。

这样一来，问题就迎刃而解啦，喵~

代码实现喵~

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

// 这是一个检查函数，非常关键喵~
// 它负责验证对于一个给定的长度L，我们能否构造出一个满足条件的周期串
// n: 字符串总长
// s: 原字符串
// L: 当前要检查的周期长度
// k_start_idx: 我们用来当作模板k的子串在s中的起始位置
bool check_candidate(int n, const std::string& s, int L, int k_start_idx) {
    int diffs = 0; // 用来记录差异字符的数量
    for (int i = 0; i < n; ++i) {
        // s[i] 是原字符串的字符
        // s[k_start_idx + (i % L)] 是我们构造的周期串在i位置应有的字符
        // (i % L) 确保了周期性，k_start_idx 决定了我们用哪个块做模板
        if (s[i] != s[k_start_idx + (i % L)]) {
            if (++diffs > 1) { // 如果差异超过1个，就没必要继续检查了
                return false;
            }
        }
    }
    return true; // 差异数是0或1，满足条件！
}

void solve() {
    int n;
    std::cin >> n;
    std::string s;
    std::cin >> s;

    // 第一步：找出n的所有约数
    std::vector<int> divisors;
    for (int i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            divisors.push_back(i);
            if (i * i != n) { // 避免重复添加，比如n=36, i=6
                divisors.push_back(n / i);
            }
        }
    }
    // 第二步：将约数从小到大排序，这样我们就能先检查最短的长度
    std::sort(divisors.begin(), divisors.end());

    // 第三步：遍历所有约数L，寻找答案
    for (int L : divisors) {
        // 检查候选一：用s的前缀s[0...L-1]作为k
        if (check_candidate(n, s, L, 0)) {
            std::cout << L << "\n";
            return; // 找到了！直接返回
        }
        
        // 检查候选二：用s的后缀s[n-L...n-1]作为k
        // 这个检查只有在 L < n 时才有意义。如果 L=n，前缀和后缀是同一个东西，上面已经检查过了。
        if (L < n) {
            if (check_candidate(n, s, L, n - L)) {
                std::cout << L << "\n";
                return; // 找到了！直接返回
            }
        }
    }
}

int main() {
    // 加速输入输出，是个好习惯哦~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析的说

• 时间复杂度: O(d(n) * n) 的说。

  • 对于每个测试用例，我们首先要找到 n 的所有约数。用 sqrt(n) 的方法，复杂度是 O(sqrt(n))。
  • n 的约数个数我们记为 d(n)。d(n) 的增长速度远小于 n，对于 n <= 2*10^5，d(n) 最大也只有160。
  • 对于每个约数 L，我们会调用 check_candidate 函数最多两次。这个函数内部有一个遍历整个字符串 s 的循环，所以它的复杂度是 O(n)。
  • 因此，总的时间复杂度就是 O(sqrt(n) + d(n) * n)。因为 d(n)*n 占主导，所以我们记为 O(d(n) * n)。考虑到所有测试用例的 n 的总和有限制，这个复杂度是完全可以接受的！

• 空间复杂度: O(n) 的说。

  • 我们需要存储输入的字符串 s，这需要 O(n) 的空间。
  • 存储 n 的约数的 vector 最多需要 O(d(n)) 的空间，这比 n 小得多。
  • 所以，主要的开销来自于字符串 s，空间复杂度是 O(n)。

知识点与总结

这道题真是一次有趣的思维锻炼呢！让我们来总结一下学到了什么吧，喵~

1. 数论性质是解题的钥匙：本题最核心的突破口就是发现周期长度 L 必须是总长度 n 的约数。在很多涉及周期、重复、循环的字符串问题中，约数和模运算都是非常有力的工具！
2. 化繁为简的构造思想：我们不需要凭空创造出 k，而是通过分析 "最多一个不同" 的性质，推断出 k 极大概率就藏在 s 的某个块中。用 s 的前缀和后缀作为候选 k，是一种非常巧妙且有效的构造方法。
3. 代码实现技巧：
   • i * i <= n 是求约数的标准高效写法。
   • 将核心的验证逻辑封装成一个独立的函数 (check_candidate)，可以让主函数 (solve) 的逻辑更加清晰易懂，这是良好编程风格的体现哦！
   • 别忘了对约数排序，这样才能保证找到的是最短的长度。

希望这篇题解能帮助你理解这道题目！只要能抓住问题的关键性质，再复杂的题目也会变得清晰起来的。继续努力，你一定能成为更厉害的算法大师，加油喵~！