CppCPU占用时长 1秒内存使用限制 128MB题目描述小C喜欢猜谜语最近一种新的的谜语引起了小C的注意它需要判断谜面是不是一个重叠字串。重叠字串由两个或更多的子串每个子串都是一些相同字母组成的排列即每个子串都可以通过改变字符的顺序使其与其他任意一个子串相等。我们将第一个子串称为整个重复字串的根。例如字符串 ������bbabab 就是一个重复字串由 ���bba���bab两个子串构成���

解题思路：

1. 首先，判断给定的字符串是否为重叠字串，如果不是则输出-1。
2. 遍历字符串的所有可能的根，从长度为1开始，依次增加根的长度。
3. 对于每个根，将字符串分为多个子串，每个子串的长度为根的长度。
4. 判断每个子串是否与根相等，如果有任意一个子串与根不相等，则当前根不是重叠字串的根。
5. 如果所有的子串都与根相等，则当前根是重叠字串的根，输出当前根即可。

C++代码实现如下：

#include #include #include

using namespace std;

bool isOverlapSubstring(string str, int rootLen) { int len = str.length(); vector substrs;

// 分割字符串为多个子串
for (int i = 0; i < len; i += rootLen) {
    substrs.push_back(str.substr(i, rootLen));
}

// 判断每个子串是否与根相等
for (int i = 0; i < substrs.size(); i++) {
    if (substrs[i] != substrs[0]) {
        return false;
    }
}

return true;

}

string findShortestRoot(string str) { int len = str.length();

// 遍历所有可能的根
for (int rootLen = 1; rootLen <= len / 2; rootLen++) {
    if (len % rootLen == 0 && isOverlapSubstring(str, rootLen)) {
        return str.substr(0, rootLen);
    }
}

return "-1";

}

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

string shortestRoot = findShortestRoot(str);
cout << shortestRoot << endl;

return 0;