String - 题解

标签与难度

标签: 贪心算法, 字符串, 最小表示法, 字典序难度: 1800

题目大意喵~

主人你好呀，这道题是关于字符串分割的喵~

题目给了我们一个定义叫做“完美字符串” (perfect string)。一个字符串如果在于它所有的循环同构串（就是把它掰弯成一个环，从不同位置断开读出的字符串）中，是字典序最小的那一个，那它就是完美的！比如说，"0101" 就是一个完美的字符串，因为它的循环同构串有 "0101", "1010", "0101", "1010"，其中 "0101" 就是最小的那个，喵~

我们的任务是，拿到一个只包含 '0' 和 '1' 的字符串，要把它分割成最少的几段，并且保证每一段都是一个完美的字符串。

输入：一个01字符串。输出：分割后的每一段，用空格隔开。

举个例子，如果输入是 010010，一个可能的分割是 0100 和 10。但 10 不是完美的（因为 01 < 10），所以这个分法不行。正确的分割应该是 0100 1 0。

解题思路分析

这道题要求我们用最少的段数来分割字符串，这是一个非常强烈的信号，暗示我们可以使用贪心算法，喵！

贪心算法的核心思想就是“只看眼前，做出最好的选择”。对于这个问题，我们站在字符串的某个位置，要决定下一段分割到哪里。为了让总段数最少，我们应该让当前这一段尽可能地长！只要它满足“完美字符串”的条件就行。

所以，我们的贪心策略就出来啦：

从字符串的当前位置开始（一开始是位置0）。
找到一个从当前位置开始的最长的前缀，这个前缀本身要是一个完美的字符串。
把这个最长的前缀作为一段分割出来。
然后，从这个前缀的末尾之后一个位置，继续重复上面的过程，直到整个字符串都被分割完为止。

比如说，对于 010010：

我们从位置 0 开始。
s[0:0] = "0"，是完美的。
s[0:1] = "01"，不是完美的（"10" > "01"，但它不是最小的，因为没有别的字符了）。哦不对，它的循环同构只有"01"和"10"，"01"更小，所以"01"是完美的！
s[0:2] = "010"，循环同构有 "010", "100", "001"。 "001" 最小，所以 "010" 不完美。
s[0:3] = "0100"，循环同构有 "0100", "1000", "0001", "0010"。 "0001" 最小，所以 "0100" 不完美。
... 等等，让本喵再仔细想想。啊！"01"的循环同构是"01"和"10"，"01" < "10"，所以"01"是完美的！
s[0:3] = "0100" 的循环同构串有 "0100", "1000", "0001", "0010"。其中 "0001" 是最小的。所以 "0100" 不是完美的。
看来我的例子举错了，喵呜~ >.< 让我们换个思路。

正确的贪心策略是：从当前位置 i 开始，我们从后往前检查所有可能的结束位置 j。也就是说，我们先尝试把整个剩余的字符串 s[i...end] 当做一段，检查它是否完美。如果不是，就试试短一点的 s[i...end-1]，再试试 s[i...end-2]... 直到找到第一个（也就是最长的）完美的子串 s[i...j] 为止。然后我们就把这一段切下来，下一次从 j+1 开始。

这个贪心策略是正确的，因为每次我们都取了最长的一段，最大化了“消耗”，自然能让总段数最少啦。

那么，现在的问题就变成了：如何判断一个字符串是不是完美的呢？

根据定义，我们需要检查一个字符串 t 是否比它所有的循环同构串的字典序都小（或相等）。

一个简单直接的方法就是，把 t 的所有循环同构串都生成出来，然后和 t 一一比较。比如对字符串 t (长度为 L)：

第1个循环同构串是 t 本身。
第2个是把 t 的第一个字符挪到最后面。
第3个是把 t 的前两个字符挪到最后面。
...
一共要比较 L-1 次。这个检查过程的时间复杂度是 $O(L^2)$ 。

虽然这个检查方法有点慢，但是结合我们的贪心策略，对于这道题的数据范围来说，应该是可以通过的。不过，本喵知道一个更快的 $O(L)$ 的方法哦，叫做最小表示法（或者叫 Booth's Algorithm / Duval's Algorithm 的思想），用两个指针 i 和 j 来比较两个候选的循环串，非常巧妙！

这里我将用一个叫做“双指针法”的技巧来实现这个 $O(L)$ 的检查，让我们的代码更高效、更优雅，喵~

双指针法检查完美字符串 t (长度为 L):

我们想找到 t 的最小循环表示法的起始位置。如果这个位置是0，那么 t 就是完美的。
我们用三个变量：i，j 和 k。i 和 j 是两个候选的起始位置，初始为 i=0, j=1。k 是它们已经匹配的长度，初始为 0。
我们比较 t[(i+k)%L] 和 t[(j+k)%L]。
- 如果它们相等，说明前缀匹配又增加了一位，就 k++。
- 如果 t[(i+k)%L] > t[(j+k)%L]，说明从 i 开始的这个循环串肯定不是最小的了，因为它在第 k 位就输给了从 j 开始的串。所以我们淘汰 i，让 i 跳到 i+k+1 的位置，然后 k 重置为 0。
- 如果 t[(i+k)%L] < t[(j+k)%L]，同理，我们淘汰 j，让 j 跳到 j+k+1 的位置，k 重置为 0。
在循环中，如果 i 和 j 相遇了，就让其中一个 +1 错开。
当 k 达到 L 或者 i, j 超出 L 时，循环结束。最终 min(i, j) 就是最小表示法的起始下标。

我们只需要用这个方法求出最小表示法的起始下标，然后判断它是不是 0 就好啦！

总结一下我们的完整算法：

设置一个指针 currentIndex = 0，表示当前处理到字符串的哪个位置。
当 currentIndex 还没有到达字符串末尾时，循环： a. 从 len = s.length() - currentIndex 开始，递减到 1。 b. 取出子串 segment = s.substr(currentIndex, len)。 c. 用我们高效的 is_perfect 函数检查 segment 是否完美。 d. 如果是完美的，那么这就是我们要找的最长的一段！打印它，然后把 currentIndex 增加 len，并跳出内层循环（len 的循环），进行下一次外层循环。
任务完成，喵~

代码实现

这是本喵根据上面的思路，精心重构的一份代码哦！注释很详细，希望能帮助主人理解，喵~

cpp

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

// 判断一个字符串 s 是否是 "完美字符串"
// 完美字符串是其所有循环同构串中字典序最小的那个
// 这里使用 O(L) 的双指针算法 (最小表示法) 来判断, L 是字符串长度
bool is_perfect(const std::string& s) {
    int n = s.length();
    if (n <= 1) {
        return true; // 长度为0或1的字符串一定是完美的
    }

    int i = 0; // 第一个候选串的起始指针
    int j = 1; // 第二个候选串的起始指针
    int k = 0; // 已匹配的长度

    while (i < n && j < n && k < n) {
        // 比较两个候选串的第 k 个字符 (注意要取模)
        char char_i = s[(i + k) % n];
        char char_j = s[(j + k) % n];

        if (char_i == char_j) {
            k++; // 字符相同，继续匹配下一位
        } else {
            // 字符不同，说明一个候选串比另一个更优
            if (char_i > char_j) {
                // 从 i 开始的串不是最优的，淘汰它
                // 我们可以安全地跳过 i 到 i+k 的所有位置
                i = i + k + 1;
            } else { // char_i < char_j
                // 从 j 开始的串不是最优的，淘汰它
                j = j + k + 1;
            }
            k = 0; // 重置匹配长度
            
            // 保证 i 和 j 不会指向同一个位置
            if (i == j) {
                j++;
            }
        }
    }

    // 循环结束后, min(i, j) 就是最小表示法的起始下标
    // 如果最小表示法的起始下标是 0, 说明原字符串 s 就是完美的
    return std::min(i, j) == 0;
}

void solve() {
    std::string s;
    std::cin >> s;
    int n = s.length();
    int current_index = 0;

    bool first_part = true; // 用于控制输出空格

    while (current_index < n) {
        // 贪心策略：从当前位置开始，寻找最长的完美子串
        // 我们从最长的可能性开始尝试 (j 表示子串长度)
        for (int len = n - current_index; len >= 1; --len) {
            std::string segment = s.substr(current_index, len);
            if (is_perfect(segment)) {
                // 找到了最长的完美子串！
                if (!first_part) {
                    std::cout << " ";
                }
                std::cout << segment;
                first_part = false;
                
                // 更新下一次开始的位置
                current_index += len;
                break; // 跳出内层循环，处理下一段
            }
        }
    }
    std::cout << "\n";
}

int main() {
    // 提高C++ IO效率，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

时间复杂度: $O(N^3)$ ，其中 $N$ 是输入字符串的长度。
- 外层的 while 循环在最坏的情况下（比如每次只分割出一个字符）会执行 $N$ 次。
- 内层的 for 循环，对于一个长度为 rem_len 的剩余字符串，会尝试 rem_len 种不同的长度。
- is_perfect 函数的检查，对于一个长度为 L 的子串，时间复杂度是 $O(L)$ 。
- 所以，找到一段分割的总成本大约是 $\sum_{L=1}^{\text{rem\_len}} O(L) = O(\text{rem\_len}^2)$ 。
- 在最坏情况下，比如每次分割出的段都很短，总时间复杂度会接近 $O(N^2 + (N-1)^2 + \dots + 1^2) = O(N^3)$ 。虽然是三次方，但对于常见的字符串长度（比如几百），这个算法是足够快的，喵~
空间复杂度: $O(N)$
- 我们需要存储输入的字符串 s，这需要 $O(N)$ 的空间。
- 在循环中，s.substr() 会创建临时子串，最长可能为 $N$ ，所以这部分也需要 $O(N)$ 的空间。

知识点总结

贪心算法 (Greedy Algorithm): 这道题是贪心思想的典型应用。当我们面对要求“最多”、“最少”、“最大”、“最小”等问题时，可以先思考一下，是不是每一步都采取局部最优解，就能得到全局最优解呢？
字符串处理: 核心在于理解和处理字符串的“循环同构”和“字典序”这两个概念。
最小表示法 (Minimum Lexicographical Rotation): 这是解决完美字符串判断的关键。虽然朴素的 $O(L^2)$ 检查也能工作，但学习 $O(L)$ 的双指针法（或者 Booth's Algorithm）能让你在处理更难的字符串问题时游刃有余，是很有用的技巧哦！
问题分解: 将一个复杂问题（最少分割）分解成一个主策略（贪心）和一个子问题（如何判断完美字符串），是解题的通用思路，呐。

希望这篇题解能帮到主人！如果还有不懂的地方，随时可以再来问本喵哦！喵~

String - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​