459. 重复的子字符串

题目

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:
输入: s = “abab”
输出: true
解释: 可由子串 “ab” 重复两次构成。

示例 2:
输入: s = “aba”
输出: false

示例 3:
输入: s = “abcabcabcabc”
输出: true
解释: 可由子串 “abc” 重复四次构成。 (或子串 “abcabc” 重复两次构成。)

提示：

• 1 <= s.length <= 104
• s 由小写英文字母组成

解题思路

字符串匹配问题–KMP算法：

• 假设字符串 s 可以由子串 p 重复 k 次构成，那么 s = p + p + … + p (k次)
• 考虑将字符串 s 与自身拼接得到 s+s，然后从这个拼接字符串中去掉首尾字符，得到 (s+s)[1:-1]
• 如果 s 是由重复子串构成的，那么 s 一定会在 (s+s)[1:-1] 中出现
• 这是因为：
  • 如果 s = p+p+…+p，那么 s+s = p+p+…+p+p+p+…+p (2k个p)
  • 去掉首尾字符后，我们打破了首尾的模式，但中间仍然完整包含了至少一个完整的 s
• 反之，如果 s 不能由重复子串构成，那么 s 不会在 (s+s)[1:-1] 中出现

代码

// KMP算法中的构建next数组函数
void buildNext(char* p, int len, int* next) {int j = 0;next[0] = 0;for (int i = 1; i < len; i++) {while (j > 0 && p[j] != p[i]) {j = next[j - 1];}if (p[j] == p[i]) {j++;}next[i] = j;}
}bool repeatedSubstringPattern(char* s) {int len = strlen(s);if (len <= 1) return false;  // 长度为1的字符串不可能由重复子串构成// 创建拼接字符串char* concat = (char*) malloc(2 * len + 1);strcpy(concat, s);strcpy(concat + len, s);// 创建去掉首尾的拼接字符串char* truncated = (char*) malloc(2 * len - 1); // +1是为了字符串结束符，但我们实际不使用strncpy(truncated, concat + 1, 2 * len - 2);truncated[2 * len - 2] = '\0';  // 确保字符串正确结束// 构建next数组int* next = (int*) malloc(len * sizeof(int));buildNext(s, len, next);// 使用KMP算法查找s是否在truncated中int i = 0; // truncated的索引int j = 0; // s的索引bool found = false;while (i < 2 * len - 2) {if (truncated[i] == s[j]) {i++;j++;if (j == len) {// 找到完整匹配found = true;break;}} else if (j > 0) {j = next[j - 1];} else {i++;}}// 释放内存free(concat);free(truncated);free(next);return found;
}

改进代码