文章目录
- 459. 重复的子字符串
- 题目描述
- 暴力
- 移动匹配
- KMP算法
459. 重复的子字符串
题目描述
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = “abab”
输出: true
解释: 可由子串 “ab” 重复两次构成。
示例 2:
输入: s = “aba”
输出: false
示例 3:
输入: s = “abcabcabcabc”
输出: true
解释: 可由子串 “abc” 重复四次构成。 (或子串 “abcabc” 重复两次构成。)
提示：
- 1 <= s.length <= 104
- s 由小写英文字母组成
暴力
这段代码的工作原理如下：
- 外层循环每次将字符串s的下一个字符加入到子串a中，这个子串可能是重复的单元。
- 内层循环尝试用子串a去匹配整个字符串s。
- 如果在某次内层循环中，a成功地匹配了整个s（其中count用于跟踪a在s中重复的次数），那么函数返回true。
- 如果a在任何点上失败（字符不匹配），内层循环将会中断，并且外层循环继续尝试下一个可能的子串。
该算法是一个基本的解法，对于每个可能的子串进行尝试，时间复杂度为O(n^2)，其中n是字符串s的长度。在最坏的情况下，例如当字符串为全部由相同字符组成时，这个解法可能会比较慢。更高效的算法可能会使用KMP算法或字符串哈希来降低复杂度。
// 定义解决方案类
class Solution {
public:
// repeatedSubstringPattern成员函数，接受一个字符串s
bool repeatedSubstringPattern(string s) {
// a用于存储当前正在检查的子串
string a="";
// 循环遍历字符串的前半部分
// 如果s能由子串重复构成，那么子串的长度不会超过s长度的一半
for(int i=0; i < s.size() / 2; i++) {
// 将当前字符添加到子串a中
a += s[i];
// count用于记录当前已匹配的字符数
int count = 0;
// k用于在子串a中的比较位置
int k = 0;
// 遍历整个字符串s
for(int j = 0; j < s.size(); j++) {
// 如果字符匹配，增加已匹配的字符数，移动k到下一个位置
if(s[j] == a[k]) {
count++;
k++;
// 如果已匹配字符数等于子串a的长度
if(count == a.size()) {
// 如果此时已经到达s的末尾，则返回true
if(j == s.size() - 1)
return true;
// 重置已匹配字符数和子串a的比较位置
count = 0;
k = 0;
}
} else {
// 一旦遇到不匹配的情况，立即跳出内层循环
break;
}
}
}
// 如果循环结束都没有找到符合条件的子串，返回false
return false;
}
};
移动匹配
当一个字符串s：abcabc，内部由重复的子串组成，那么这个字符串的结构一定是这样的：
也就是由前后相同的子串组成。
那么既然前面有相同的子串，后面有相同的子串，用 s + s，这样组成的字符串中，后面的子串做前串，前面的子串做后串，就一定还能组成一个s，如图：
所以判断字符串s是否由重复子串组成，只要两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成。
当然，我们在判断 s + s 拼接的字符串里是否出现一个s的的时候，要刨除 s + s 的首字符和尾字符，这样避免在s+s中搜索出原来的s，我们要搜索的是中间拼接出来的s。
代码如下：
// 定义解决方案类
class Solution {
public:
// 定义成员函数repeatedSubstringPattern，它接受一个字符串s
bool repeatedSubstringPattern(string s) {
// 创建一个新字符串t，由字符串s重复拼接一次得来，这样任何s的重复子串模式都会在新字符串t中出现两次
string t = s + s;
// 从t的开头删除一个字符，这是为了除去原始字符串的单独完整出现
t.erase(t.begin());
// 从t的尾部删除一个字符，同样是为了确保消除原始字符串的单独完整出现
t.erase(t.end() - 1);
// 在新字符串t中寻找原始字符串s
// 如果发现s存在于t中（并且不是在开头或者结尾，因为那些位置已经被删除了）
// 那么说明s可以由它的一个子串通过重复多次构成
if (t.find(s) != -1) return true;
// 如果在t中找不到s作为子串，说明s不能由它的子串通过重复构成，返回false
return false;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1)
- 不过这种解法还有一个问题，就是 我们最终还是要判断 一个字符串（s + s）是否出现过 s 的过程，大家可能直接用contains，find 之类的库函数。 却忽略了实现这些函数的时间复杂度（暴力解法是m * n，一般库函数实现为 O(m + n)）。
如果我们做过 28. 找出字符串中第一个匹配项的下标 题目的话，其实就知道，实现一个 高效的算法来判断 一个字符串中是否出现另一个字符串是很复杂的，这里就涉及到了KMP算法。
KMP算法
详细解析可以看这篇文章：459.重复的子字符串
// 定义解决方案类
class Solution {
public:
// repeatedSubstringPattern成员函数接受一个字符串s
bool repeatedSubstringPattern(string s) {
// 获取字符串的长度
int len = s.size();
// 定义next数组，大小与s的长度相同
int next[len];
// 用私有成员函数getnext来填充next数组
getnext(next, s);
// 检查next数组的最后一个元素
// 如果next[len-1]不为0，并且s的长度能够被（s的长度 - next[len-1]）整除
// 则s由重复的子串构成
if (next[len - 1] != 0 && (len % (len - next[len - 1]) == 0))
return true; // 存在重复的子串模式
// 如果不满足上述条件，则不存在重复的子串模式
return false;
}
private:
// 定义getnext函数，用于填充next数组
void getnext(int* next, string& s) {
// 初始化j为0（j代表当前正在比较的s的前缀的长度）
int j = 0;
// next数组的第一项总是0，因为一个字符没有前缀和后缀
next[0] = 0;
// 遍历字符串s的每个字符，计算next数组的值
for (int i = 1; i < s.size(); i++) {
// 如果当前字符与前缀的下一个字符不匹配，回退到前一个匹配的位置
while (j > 0 && s[i] != s[j])
j = next[j - 1];
// 如果当前字符匹配前缀的下一个字符，j增加1
if (s[i] == s[j])
j++;
// 将j作为next数组的当前元素的值
next[i] = j;
}
}
};
这段代码的逻辑是这样的：
- 在主函数repeatedSubstringPattern中，我们首先创建一个与输入字符串s等长的next数组。
- 然后调用getnext函数来填充next数组。这个函数计算字符串s的每个前缀的最长相等前后缀长度。
- 接下来检查next数组的最后一个元素（next[len - 1]）。如果这个值不为0，并且s的长度能被s长度减去next[len - 1]的结果整除，那么字符串s就是由重复的子串构成的。
简单来说，如果s是由重复的子串构成的，那么next数组的最后一个元素将会是一个不为0的值，这个值是重复子串的长度的整数倍。例如，对于字符串s = “abcabc”，next数组的最后一个值是3，表明有一个长度为3的子串重复出现了。由于字符串长度为6，6 % (6 - 3) 等于0，这意味着字符串可以由长度为3的子串重复两次构成，符合题目的要求。
