C++ 题解题目：5513 单词谜关卡：枚举时空限制CPU占用时长 100秒内存使用限制 128MB题目描述有一种英文字谜游戏一开始创作者选一个称为根的单词 �R然后可能多次打乱 �R连接到 �R 单词后面。例如：���������bbabababb是根单词 ���bba与乱序单词 ���bab、���abb 连接组成。字谜参加者要面对一个字符串找出最短的根单词。如果找不到输出 −1−1。输入格式

解题思路：由题意可知，要找到最短的“根”单词，即为输入字符串的前缀。

具体实现步骤如下：

1. 读入字符串。
2. 从第一个字符开始遍历字符串，判断当前遍历到的子串是否为输入字符串的前缀。
3. 如果是前缀，则输出该子串作为最短的“根”单词，结束程序。
4. 如果遍历完字符串都没有找到前缀，则输出-1。

C++代码实现如下：

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;

    for (int i = 1; i <= s.length(); i++) {  // 遍历字符串的所有子串
        string prefix = s.substr(0, i);  // 获取当前子串作为前缀
        bool isPrefix = true;

        // 判断当前前缀是否是输入字符串的前缀
        for (int j = i; j < s.length(); j++) {
            if (s[j] != prefix[j % i]) {
                isPrefix = false;
                break;
            }
        }

        if (isPrefix) {
            cout << prefix << endl;
            return 0;
        }
    }

    cout << -1 << endl;
    return 0;
}

时间复杂度分析：遍历字符串的所有子串需要O(n^2)的时间复杂度，其中n为字符串的长度。由于题目限制了字符串的长度不超过100,000，因此算法的时间复杂度是可以接受的。

空间复杂度分析：除了输入字符串外，算法只使用了常数级别的额外空间，因此空间复杂度为O(1)