题目描述
代码解决
class Solution
{
public:// 计算字符串s的next数组，用于KMP算法void getNext(int *next, const string& s){int j = 0; // j是前缀的长度next[0] = 0; // 初始化next数组，第一个字符的next值为0for (int i = 1; i < s.size(); i++) // 注意这里的i从1开始{// 如果s[i] != s[j]，则向前回溯，直到找到匹配的前缀或到达字符串开始while (j > 0 && s[i] != s[j]){j = next[j - 1];}// 如果s[i] == s[j]，前缀长度增加1if (s[i] == s[j]){j++;}next[i] = j; // 更新next数组}}bool repeatedSubstringPattern(string s) {if (s.size() == 0){return false;}int next[s.size()];getNext(next, s); // 计算next数组int len = s.size();int pattern_length = len - next[len - 1]; // 计算模式字符串的长度// 如果next[len - 1] != 0 且 len 能被 pattern_length 整除，则表示有重复的模式if (next[len - 1] != 0 && len % pattern_length == 0) {return true;}return false;}
};
-
计算Next数组：
getNext函数通过计算next数组来确定每个字符前缀的最大长度，使得这些前缀同时也是后缀。- 具体地，对于每一个字符
s[i]，如果它不能匹配当前的前缀字符s[j]，则通过j = next[j - 1]回溯到前一个匹配位置，直到找到匹配的前缀或到达字符串的开始。
-
检查重复子串模式：
- 如果
next[len - 1]不为0，表示字符串存在部分重复。 - 计算模式字符串的长度
pattern_length，这个长度等于字符串的总长度减去最后一个前缀值next[len - 1]。 - 如果字符串长度
len可以被pattern_length整除，则表示字符串可以由重复的模式字符串构成。
- 如果
