单词谜(详解版)
【题目描述】
有一种英文字谜游戏，一开始创作者选一个称为"根"的单词R，然后可能多次打乱 R，连接到 R 单词后面。例如：bbabababb，是根单词 bba，与乱序单词 bab、abb 连接组成。 字谜参加者要面对一个字符串，找出最短的"根"单词。如果找不到输出-1。
【输入格式】 第 1 行：长度不超过 100,000 的小写英文字母组成的字符串。
【输出格式】 最短的根单词（是输入字符串的前缀）。如果找不到根单词，输出-1。
【输入输出样例】
输入1
aaaa
输出1
a
输入2
ab
输出2
-1
输入3
bbabab
输出3
bba
浅说：这道题的有点不好理解，下面对本题的思路，步骤和样例都进行了详细地解析，方便大家能更好地理解~完整的代码在最后哦~
整体解题思路概述
代码的目标是解决寻找给定字符串中最短 “根” 单词的问题。“根” 单词需满足是输入字符串的前缀，且输入字符串后续部分可以看作是这个 “根” 单词打乱后的形式多次连接而成。代码整体思路是先处理输入字符串中所有字符都相同的特殊情况，然后通过循环尝试不同长度去划分字符串，验证每个长度下是否能找到符合要求的 “根” 单词，若找到则输出，没找到则输出 -1。
代码各部分详细解释
#include<bits/stdc++.h>
using namespace std;
string s;
int a[26],b[26];
int main(){
cin>>s;
int n = s.size();- int a[26],b[26] ：定义了两个长度为 26 的整数数组 a 和 b，用于分别统计可能的 “根” 单词以及后续同长度子串中每个英文字母出现的频次，通过数组下标对应 26 个英文字母（a[0] 对应 'a'，a[1] 对应 'b' 以此类推）。
- int n = s.size()：获取输入字符串 s 的长度，并存储在变量 n 中，后续很多循环和判断都会基于这个长度值进行操作。
处理字符串所有字符相同的特殊情况
bool gege1 = false;
for(int i = 0;i < n - 1;i++){
if(s[i]!= s[i + 1]){
gege1 = true;
break;
}
}
if(!gege1){
cout<<s[0];
return 0;
}- 首先初始化一个布尔变量 gege1 为 false，表示假设字符串所有字符相同的情况。然后通过一个循环遍历字符串 s 中除了最后一个字符之外的所有字符（索引范围是从 0 到 n - 2），比较相邻两个字符是否相同。
- 如果在循环过程中发现有相邻字符不一样（即 s[i]!= s[i + 1]），就把 gege1 置为 true，并立即跳出循环。
- 循环结束后，如果 gege1 仍然是 false，说明整个字符串的字符都相同，按照题目规则，此时最短的 “根” 单词就是字符串的第一个字符，所以直接输出 s[0]，然后通过 return 0; 结束整个程序。
核心逻辑：寻找合适长度的 “根” 单词部分
gege1 = false;
for (int i = 2; i < n; i++) {
if (n % i == 0) {
gege1 = true;
string str1 = s.substr(0, i);
memset(a, 0, sizeof(a));
for (int j = 0; j < str1.size(); j++) {
a[str1[j] - 'a']++;
}
for (int z = i; z < n; z += i) {
string str2 = s.substr(z, i);
memset(b, 0, sizeof(b));
for (int w = 0; w < str2.size(); w++) {
b[str2[w] - 'a']++;
}
bool gege2 = true;
for (int k = 0; k < 26; k++) {
if (a[k]!= b[k]) {
gege2 = false;
break;
}
}
if (!gege2) {
gege1 = false;
break;
}
}
if (gege1) {
cout << s.substr(0, i);
return 0;
}
}
}- 先将
gege1重新置为false，然后进入一个外层循环，从长度2开始（因为长度为1的情况已经在前面特殊处理了），一直到小于字符串长度n的值去尝试不同长度i来划分字符串。 - 当
n % i == 0时，意味着字符串长度能被当前尝试的长度i整除，这种情况下有可能按照这个长度划分出符合要求的 “根” 单词及后续子串，所以： - gege1 = true;：先假设当前长度 i 是符合要求的，后续如果出现不符合的情况会再把它置为 false。
- string str1 = s.substr(0, i);：取出字符串 s 开头长度为 i 的子串，将其作为当前尝试的可能的 “根” 单词，并存储在 str1 变量中。
- memset(a, 0, sizeof(a));：使用 memset 函数将数组 a 清零，目的是为了重新统计当前可能 “根” 单词 str1 中各字母出现的频次，避免之前尝试其他长度时残留的数据影响本次统计。
- 接着通过一个循环，统计 str1 中每个字母出现的频次并存入数组 a 中，具体是通过将字符减去 'a' 得到对应的数组下标，然后对相应下标的元素进行自增操作（a[str1[j] - 'a']++;）。
- 之后进入内层循环，从位置 i 开始，每次间隔长度 i 取出后续的子串（string str2 = s.substr(z, i);），同样地：
- memset(b, 0, sizeof(b));：先将用于统计当前子串字母频次的数组 b 清零，确保统计是基于干净的数据状态。
- 通过循环统计子串 str2 中各字母出现的频次并存入数组 b 中（b[str2[w] - 'a']++;）
- 再通过一个循环比较数组 a 和 b 对应位置的元素（也就是比较 “根” 单词与后续同长度子串中各字母的频次是否一致），只要发现有一个位置上的元素不相等（即 a[k]!= b[k]），就把表示当前子串与 “根” 单词比较结果的布尔变量 gege2 置为 false，并立即跳出这个比较循环。
- 如果 gege2 变为了 false，说明当前长度 i 不符合要求（存在子串与 “根” 单词的字母频次不一致的情况），则把 gege1 置为 false，并跳出内层循环，继续尝试下一个长度 i。
- 如果内层循环完整结束后，gege1 仍然为 true，这意味着对于当前长度 i，所有后续子串与开头取出的可能 “根” 单词在字母频次上都是一致的，也就是找到了符合要求的 “根” 单词，此时输出这个长度为 i 的开头子串（cout << s.substr(0, i);），然后通过 return 0; 结束整个程序。
处理未找到合适 “根” 单词的情况
if(!gege1) cout<<"-1";
return 0;- 如果经过前面所有对不同长度 i 的尝试，外层循环结束后 gege1 仍然为 false，说明没有找到符合要求的 “根” 单词，按照题目规定输出 -1，然后结束整个程序。
样例一：输入 aaaa，输出 a
1）读取输入与初始化相关变量
代码首先执行 cin>>s;，将输入的字符串 "aaaa" 存储到 string 类型的变量 s 中，然后通过 int n = s.size(); 计算出字符串的长度 n = 4。
2）处理字符串所有字符相同的特殊情况判断：
进入以下循环：
bool gege1 = false;
for(int i = 0;i < n - 1;i++){
if(s[i]!= s[i + 1]){
gege1 = true;
break;
}
}这个循环用于判断字符串中相邻字符是否相同，在这里，从索引 0 开始遍历到索引 2（因为 i < n - 1，n = 4，所以最大索引为 2），比较每个位置的字符和它下一个位置的字符。由于整个字符串 "aaaa" 的所有字符都相同，循环中的 if 条件始终不满足，循环结束后 gege1 仍然为 false。
3）接着执行 if(!gege1) 这个条件判断，因为 gege1 是 false，所以进入代码块：
if(!gege1){
cout<<s[0];
return 0;
}按照规则，当字符串所有字符都相同时，最短的 “根” 单词就是第一个字符，所以直接输出 s[0]，也就是字符 a，然后通过 return 0; 结束整个程序，符合预期输出。
样例二：输入 ab，输出 -1
1） 读取输入与初始化相关变量：
执行 cin>>s; 将输入字符串 "ab" 存储到 s 中，再通过 int n = s.size(); 得到字符串长度 n = 2。
2）处理字符串所有字符相同的特殊情况判断：
bool gege1 = false;
for(int i = 0;i < n - 1;i++){
if(s[i]!= s[i + 1]){
gege1 = true;
break;
}
}当 i = 0 时，比较 s[0]（即 'a'）和 s[1]（即 'b'），发现它们不相同，此时会执行 gege1 = true; 并通过 break 跳出循环，gege1 变为 true。
3） 寻找合适长度的 “根” 单词部分（核心逻辑）：
gege1 = false;
for (int i = 2; i < n; i++) {
// 后续代码块
}由于 n = 2，循环条件 i < n（此时 i 从 2 开始）不满足，这个循环根本不会执行，意味着没有尝试任何长度去划分字符串寻找 “根” 单词。
4）处理未找到合适 “根” 单词的情况：
if(!gege1) cout<<"-1";
return 0;因为前面 gege1 在判断相邻字符不同时已经被置为 true 了，而寻找 “根” 单词的循环又没执行改变它的值，所以此时 !gege1 为 false，不会输出 -1。但实际上由于前面的步骤都没有找到合适的 “根” 单词，按照题目要求就是要输出 -1，整体符合预期结果。
样例三：输入
bbabab，输出bba
1）读取输入与初始化相关变量：
通过 cin>>s; 把输入字符串 "bbabab" 存入 s 中，再由 int n = s.size(); 算出字符串长度 n = 6
2）处理字符串所有字符相同的特殊情况判断：
进入判断相邻字符是否相同的循环：
bool gege1 = false;
for(int i = 0;i < n - 1;i++){
if(s[i]!= s[i + 1]){
gege1 = true;
break;
}
}当 i = 0 时，比较 s[0]（即 'b'）和 s[1]（即 'b'）是相同的，但当 i = 1 时，比较 s[1]（即 'b'）和 s[2]（即 'a'）发现不同，此时会执行 gege1 = true; 并跳出循环，gege1 变为 true。
3）寻找合适长度的 “根” 单词部分（核心逻辑）：
进入寻找合适长度 “根” 单词的循环：
gege1 = false;
for (int i = 2; i < n; i++) {
if (n % i == 0) {
// 后续代码块
}
} 首先 i = 2 时，n % i = 6 % 2 = 0，满足条件进入内层代码块：
gege1 = true;：先假设当前长度i = 2是符合要求的（后续再验证）。string str1 = s.substr(0, 2);：取出开头长度为2的子串，即"bb"，存储到str1中。memset(a, 0, sizeof(a));：将用于统计str1中字母频次的数组a清零。- 通过循环统计 str1 中各字母频次到 a 数组，这里 a[0]（对应 'a'）为 0，a[1]（对应 'b'）为 2
- 接着进入内层循环，从 z = i = 2 开始，每次间隔长度 i = 2 取出后续子串：
- 第一次取到的子串 str2 = s.substr(2, 2); 为 "ab"，先执行 memset(b, 0, sizeof(b)); 清零 b 数组，再通过循环统计 str2 中字母频次存到 b 数组，此时 b[0]（对应 'a'）为 1，b[1]（对应 'b'）为 1。
- 然后比较 a 和 b 数组各元素，发现 a[0]!= b[0] 或者 a[1]!= b[1]，会把 gege2 置为 false，进而把 gege1 置为 false，并跳出这个内层循环，继续尝试下一个 i。
- 接着 i = 3 时，n % i = 6 % 3 = 0，又满足条件进入内层代码块：
- 同样的步骤，gege1 = true;，string str1 = s.substr(0, 3); 取出开头长度为 3 的子串，即 "bba"，存储到 str1 中。
- emset(a, 0, sizeof(a)); 清零 a 数组，通过循环统计 str1 中各字母频次到 a 数组，这里 a[0]（对应 'a'）为 1，a[1]（对应 'b'）为 2。
- 进入内层循环，从
z = 3开始，每次间隔长度i = 3取子串： - 第一次取到的子串 str2 = s.substr(3, 3); 为 "bab"，先 memset(b, 0, sizeof(b)); 清零 b 数组，再统计其字母频次存到 b 数组，此时 b[0]（对应 'a'）为 1，b[1]（对应 'b'）为 2，比较 a 和 b 数组各元素，都是相等的。
- 第二次取到的子串 str2 = s.substr(6, 3); 由于已经超出字符串范围（长度总共 6），不会执行这一次取子串操作，但前面取到的子串比较结果都通过了，内层循环结束后，由于所有比较都通过了，gege1 仍然为 true，说明找到了符合要求的 “根” 单词，执行 cout << s.substr(0, 3); 输出 "bba"，然后通过 return 0; 结束整个程序，符合预期输出。
完整代码
#include<bits/stdc++.h>
using namespace std;
string s;
int a[26],b[26];
int main(){
cin>>s;
int n = s.size();
bool gege1 = false;
for(int i = 0;i < n - 1;i++){
if(s[i] != s[i + 1]){
gege1 = true;
break;
}
}
if(!gege1){
cout<<s[0];
return 0;
}
gege1 = false;
for (int i = 2; i < n; i++) {
if (n % i == 0) {
gege1 = true;
string str1 = s.substr(0, i);
memset(a, 0, sizeof(a));
for (int j = 0; j < str1.size(); j++) {
a[str1[j] - 'a']++;
}
for (int z = i; z < n; z += i) {
string str2 = s.substr(z, i);
memset(b, 0, sizeof(b));
for (int w = 0; w < str2.size(); w++) {
b[str2[w] - 'a']++;
}
bool gege2 = true;
for (int k = 0; k < 26; k++) {
if (a[k]!= b[k]) {
gege2 = false;
break;
}
}
if (!gege2) {
gege1 = false;
break;
}
}
if (gege1) {
cout << s.substr(0, i);
return 0;
}
}
}
if(!gege1) cout<<"-1";
return 0;
}创造不易，如果对您有所帮助，请一键三连哦～你的支持是我继续创造的动力源泉～