问题描述
小明在玩一个字符串拼接游戏时发现了一个有趣的现象：某些字符串可以通过重复一个较短的子串多次来构成。比如字符串 "abcabcabc" 可以由子串 "abc" 重复3次得到。这个较短的子串被称为字符串的"循环节"或"基础重复单元"。
现在小明想请你帮忙设计一个算法，给定一个非空字符串 s，找出能够通过重复构成整个字符串 s 的最短基础子串（即最短循环节）。如果存在多个这样的子串，返回任意一个即可。如果字符串无法由任何子串（除了整个字符串本身）重复构成，则返回整个字符串。
要求：
- 设计一个高效的算法来找到最短循环子串。
- 注意处理字符串可能无法由子串循环构成的情况（此时返回整个字符串）。
测试样例
样例1：
输入：
s = "abcabcabc"输出："abc"解释：整个字符串长度为9，可以由长度为3的子串"abc"重复3次（3×3=9）构成。
样例2：
输入：
s = "aaaa"输出："a"解释：整个字符串长度为4，可以由长度为1的子串"a"重复4次（1×4=4）构成。
样例3：
输入：
s = "ababab"输出："ab"解释：整个字符串长度为6，可以由长度为2的子串"ab"重复3次（2×3=6）构成。
样例4：
输入：
s = "abcde"输出："abcde"解释：整个字符串长度为5，无法由任何更短的子串重复构成（因为5是质数），因此返回整个字符串。
约束条件
- 1 ≤ s.length ≤ 1000
- s 仅由小写英文字母组成
- 保证输入的字符串 s 非空
程序代码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char* shortestRepeatingSubstring(char* s) {
int n = strlen(s);
// 枚举循环节长度
for (int len = 1; len <= n; len++) {
// 长度必须能整除 n
if (n % len != 0) continue;
// 验证 s 是否由长度为 len 的前缀重复构成
int valid = 1;
for (int i = len; i < n; i++) {
if (s[i] != s[i % len]) {
valid = 0;
break;
}
}
if (valid) {
// 找到最短循环节，返回前 len 个字符
char* result = (char*)malloc((len + 1) * sizeof(char));
strncpy(result, s, len);
result[len] = '\0';
return result;
}
}
// 理论上不会到这里（因为 len=n 总是有效的）
char* result = (char*)malloc((n + 1) * sizeof(char));
strcpy(result, s);
return result;
}
int main() {
char* r1 = shortestRepeatingSubstring("abcabcabc");
char* r2 = shortestRepeatingSubstring("aaaa");
char* r3 = shortestRepeatingSubstring("ababab");
char* r4 = shortestRepeatingSubstring("abcde");
printf("%s\n", r1); // abc
printf("%s\n", r2); // a
printf("%s\n", r3); // ab
printf("%s\n", r4); // abcde
free(r1);
free(r2);
free(r3);
free(r4);
return 0;
}
#include <stdio.h> #include <string.h> #include <stdlib.h> char* shortestRepeatingSubstring(char* s) { int n = strlen(s); // 枚举循环节长度 for (int len = 1; len <= n; len++) { // 长度必须能整除 n if (n % len != 0) continue; // 验证 s 是否由长度为 len 的前缀重复构成 int valid = 1; for (int i = len; i < n; i++) { if (s[i] != s[i % len]) { valid = 0; break; } } if (valid) { // 找到最短循环节，返回前 len 个字符 char* result = (char*)malloc((len + 1) * sizeof(char)); strncpy(result, s, len); result[len] = '\0'; return result; } } // 理论上不会到这里（因为 len=n 总是有效的） char* result = (char*)malloc((n + 1) * sizeof(char)); strcpy(result, s); return result; } int main() { char* r1 = shortestRepeatingSubstring("abcabcabc"); char* r2 = shortestRepeatingSubstring("aaaa"); char* r3 = shortestRepeatingSubstring("ababab"); char* r4 = shortestRepeatingSubstring("abcde"); printf("%s\n", r1); // abc printf("%s\n", r2); // a printf("%s\n", r3); // ab printf("%s\n", r4); // abcde free(r1); free(r2); free(r3); free(r4); return 0; }
