C++ 重叠字串判断与最短根查找 - 算法详解与代码实现

"C++ 重叠字串判断与最短根查找 - 算法详解与代码实现" \n本文讲解如何使用 C++ 代码判断一个字符串是否为重叠字串，并查找最短的根。详细阐述了算法思路、代码实现和示例，帮助读者理解重叠字串的概念和相关算法。\n\n什么是重叠字串？\n重叠字串由两个或更多的子串组成，每个子串都是一些相同字母组成的排列。例如，字符串 "bbabab" 是一个重叠字串，由 "bba","bab" 两个子串构成，"bba" 为重叠字串的根。\n\n算法思路：\n1. 首先，判断给定的字符串是否为重叠字串，如果不是则输出-1。\n2. 遍历字符串的所有可能的根，从长度为1开始，依次增加根的长度。\n3. 对于每个根，将字符串分为多个子串，每个子串的长度为根的长度。\n4. 判断每个子串是否与根相等，如果有任意一个子串与根不相等，则当前根不是重叠字串的根。\n5. 如果所有的子串都与根相等，则当前根是重叠字串的根，输出当前根即可。\n\nC++ 代码实现如下：\n\ncpp\n#include <iostream>\n#include <string>\n#include <vector>\n\nusing namespace std;\n\nbool isOverlapSubstring(string str, int rootLen) {\n int len = str.length();\n vector<string> substrs;\n \n // 分割字符串为多个子串\n for (int i = 0; i < len; i += rootLen) {\n substrs.push_back(str.substr(i, rootLen));\n }\n \n // 判断每个子串是否与根相等\n for (int i = 0; i < substrs.size(); i++) {\n if (substrs[i] != substrs[0]) {\n return false;\n }\n }\n \n return true;\n}\n\nstring findShortestRoot(string str) {\n int len = str.length();\n \n // 遍历所有可能的根\n for (int rootLen = 1; rootLen <= len / 2; rootLen++) {\n if (len % rootLen == 0 && isOverlapSubstring(str, rootLen)) {\n return str.substr(0, rootLen);\n }\n }\n \n return \"-1\";\n}\n\nint main() {\n string str;\n cin >> str;\n \n string shortestRoot = findShortestRoot(str);\n cout << shortestRoot << endl;\n \n return 0;\n}\n\n\n代码示例：\n\n输入：bbabab\n输出：bba\n\n输入：abcde\n输出：-1