NekoNowcoder

Appearance

InfiniteStringComparision - 题解 ​

标签与难度 ​

标签: 字符串, 字典序, 比较, 数学, 构造, 贪心 难度: 1400

题目大意喵~ ​

主人你好呀，这道题是关于字符串的奇妙比较哦，喵~

题目是这样子的：我们有一个特殊的字符串操作，对于任何一个字符串 x，我们可以得到一个无限长的字符串 x^∞，就是把 x 自己不断地重复、重复、再重复……就像一只猫咪追着自己的尾巴转圈圈一样，永远停不下来，嘿嘿~

比如说，如果 a = "ab"，那么 a^∞ 就是 "ababab..."。如果 b = "abc"，那么 b^∞ 就是 "abcabcabc..."。

现在，题目会给我们两个普通的字符串 a 和 b，需要我们去比较它们生成的无限字符串 a^∞ 和 b^∞ 的字典序大小。

  • 如果 a^∞ 比 b^∞ 大，就输出 >。
  • 如果 a^∞ 比 b^∞ 小，就输出 <。
  • 如果它们俩一模一样，就输出 =。

很简单对不对？就是比较两个无限长的东西啦！

解题思路分析 ​

喵呜~ 看到“无限长”，是不是感觉有点小小的头疼呀？别怕别怕，我来给你分析一下，其实这里面藏着一个非常、非常优雅的技巧哦！

1. 最初的想法：模拟比较？ ​

我们知道，比较两个字符串的字典序，是从第一个字符开始，一个一个地向后比较。对于 a^∞ 和 b^∞ 也是一样。

a^∞ 的第 i 个字符是 a[i % |a|]（其中 |a| 是字符串 a 的长度）。 b^∞ 的第 i 个字符是 b[i % |b|]。

我们可以写一个循环，从 i = 0 开始，不停地比较 a[i % |a|] 和 b[i % |b|]。如果找到第一个不相等的地方，大小关系就确定啦！

但是……如果 a^∞ 和 b^∞ 恰好相等呢？这个循环什么时候才能停下来？总不能真的跑到无限吧，我的爪爪会累坏的！

2. 怎样才算“足够长”？ ​

为了判断相等，我们需要比较一个足够长的前缀。多长才算“足够长”呢？

因为字符串 a 和 b 的模式是周期性的，周期分别是 |a| 和 |b|。当比较的长度达到它们长度的最小公倍数 lcm(|a|, |b|) 时，两个字符串都刚好完成了整数次的重复。如果到这里它们都还一模一样，那之后也肯定一模一样啦！

所以，一个可行的办法是，我们构造出 a^∞ 和 b^∞ 各自长为 lcm(|a|, |b|) 的前缀，然后直接比较这两个前缀。

但是，lcm(N, M) = (N * M) / gcd(N, M)。如果 |a| 和 |b| 都很大（比如 10510^5），那它们的最小公倍数可能会非常非常大，直接构造这么长的字符串，时间和空间都会爆炸的，喵！这个方法太笨重了。

3. 我的魔法：一个绝妙的技巧！ ​

锵锵~ 这就是本题最关键的地方！有一个神奇的结论：

要比较 a^∞ 和 b^∞，我们只需要比较 a+b 和 b+a 的字典序就可以了！

  • 如果 a+b > b+a，那么 a^∞ > b^∞。
  • 如果 a+b < b+a，那么 a^∞ < b^∞。
  • 如果 a+b = b+a，那么 a^∞ = b^∞。

是不是超级简洁，像魔法一样？我们来试试看，喵~

举个栗子 🌰 1:a = "ab", b = "abc"

  • a^∞ = "ababab..."
  • b^∞ = "abcabcabc..." 比较一下，a^∞ 的第1个字符 'b' 就比 b^∞ 的第1个字符 'b' 小，所以 a^∞ < b^∞。 现在用我们的魔法技巧：
  • a+b = "ab" + "abc" = "ababc"
  • b+a = "abc" + "ab" = "abcab" 比较 "ababc" 和 "abcab"，显然是 "ababc" < "abcab"。结果完全一致，成功！

举个栗子 🌰 2:a = "b", b = "ba"

  • a^∞ = "bbbbbb..."
  • b^∞ = "bababa..." 比较一下，在第1位（从0开始数），a^∞ 是 'b'，b^∞ 是 'a'，所以 a^∞ > b^∞。 再用我们的魔法技巧：
  • a+b = "b" + "ba" = "bba"
  • b+a = "ba" + "b" = "bab" 比较 "bba" 和 "bab"，显然是 "bba" > "bab"。结果也完全一致，太棒了！

为什么这个魔法会生效呢？

你可以这样直观地理解：我们比较 a^∞ 和 b^∞，实际上是在判断，用 a 和 b 这两个“积木”来搭建无限长的字符串时，哪一个“积木”更“优秀”，更应该排在前面。

比较 a+b 和 b+a，就像是进行了一次“交叉实验”。通过比较这两种拼接方式，我们能有效地判断出在无限重复的场景下，哪个基本单元会占据字典序上的优势。这个比较巧妙地处理了两个字符串长度不同时，周期错位的问题。

这个技巧在很多要求“拼接成最大/最小数字”的贪心问题中也经常出现，是一个非常实用的小知识点哦！记下来，下次就能帅气地秒杀这类问题啦，喵~

代码实现 ​

现在，让我们用这个超级优雅的思路来写代码吧！代码会变得非常非常简单哦。

cpp
#include <iostream>
#include <string>
#include <vector>

// 使用我最喜欢的命名空间~
using namespace std;

void solve() {
    // a 和 b 是我们的两个小积木喵~
    string a, b;

    // 循环读入，直到没有输入为止
    while (cin >> a >> b) {
        // 构造两个新的字符串：ab 和 ba
        string ab = a + b;
        string ba = b + a;

        // 直接比较这两个新构造的字符串，喵~
        if (ab > ba) {
            cout << ">" << endl;
        } else if (ab < ba) {
            cout << "<" << endl;
        } else {
            cout << "=" << endl;
        }
    }
}

int main() {
    // 为了让输入输出更快一点，虽然这题数据量不大，但这是个好习惯哦
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solve();

    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(∣a∣+∣b∣)O(|a| + |b|) 这里 |a| 和 |b| 分别是两个输入字符串的长度。我们的操作主要有两个：

    1. 字符串拼接：a+b 和 b+a，这会创建两个长度为 |a|+|b| 的新字符串，时间复杂度是 O(∣a∣+∣b∣)O(|a|+|b|)。
    2. 字符串比较：比较 ab 和 ba，最坏情况下需要比较完整个字符串，时间复杂度也是 O(∣a∣+∣b∣)O(|a|+|b|)。 所以总的时间复杂度就是 O(∣a∣+∣b∣)O(|a|+|b|)，非常高效！

  • 空间复杂度: O(∣a∣+∣b∣)O(|a| + |b|) 我们创建了两个额外的字符串 ab 和 ba 来进行比较，它们占用的空间和它们的长度成正比，所以是 O(∣a∣+∣b∣)O(|a|+|b|)。

知识点总结 ​

这道题虽然看起来有点唬人（无限！），但核心却是一个非常精巧的知识点，值得我们好好记住，喵~

  1. 无限循环字符串的比较: 解决这类问题的关键是找到一种方法，在有限的步骤内判断出无限序列的优劣。
  2. a+b vs b+a 技巧: 这是本题的“题眼”。a^∞ 和 b^∞ 的比较等价于 a+b 和 b+a 的比较。这个技巧不仅适用于本题，也适用于一类贪心问题，比如“将一组数字拼接成最大的数”。
  3. 化繁为简: 遇到看似复杂的问题时（比如涉及“无限”），不要害怕，试着从小例子入手，寻找规律，或者思考有没有等价的、更简单的判断方式。有时候，最优雅的解法就藏在最简单的操作里！

希望这篇题解能帮到你哦！如果还有不明白的地方，随时可以再来问我，我随时待命，喵~