参考资料
KMP算法易懂版
从头到尾彻底理解KMP
KMP算法之求next数组代码讲解
我觉得最主要是理解这个图，理解为什么要递归next[k]
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
解法一 枚举
遍历所有可能的情况，算法超时
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int len = s.length();
if(len < 2) return false;
for(int i = 1; i <= len/2;i++){
if(len % i != 0) continue;
string ans = "";
string tmp = s.substr(0,i);
for(int j = 1;j <= len/i;j++){
ans = ans + tmp;
}
if(ans.compare(s)==0) return true;
}
return false;
}
};
解法二
参考官方题解
class Solution {
public:
bool repeatedSubstringPattern(string s) {
return (s + s).find(s, 1) != s.size();
}
};
解法三 KMP
数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int k = -1,p = 0;
int n = s.length();
vector<int> next(n + 1);
next[0] = -1;
while(p < n){
if(k == -1 || s[p] == s[k]){
p++;k++;
next[p] = k;
}
else
k = next[k];
}
int m = n - next[n];
if(next[n] != 0 && n % m == 0) return true;
else return false;
}
};
算next数组的时候，p是要求的字符串第p个位置的next[p]，k是要比较的字符串索引，这种方式求的next数组第一位是-1，与最长前缀后缀恰好错开一位，所以让next数组大小为n+1，最后一位n+1存储的其实是第n位求的next。
防止自己忘记，记录一下。
leetcode28 正规的求kmp代码
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.length() == 0) return 0;
vector<int> next(needle.length());
next[0] = -1;
int p = 0,k = -1;
while(p < needle.length() - 1){
if(k == -1 || needle[p] == needle[k]){
p++;k++;
next[p] = k;
}
else k = next[k];
}
int i = 0,j = 0;
int x = haystack.length();
int y = needle.length();
while(i <x && j < y){
if(j == -1 || haystack[i] == needle[j]){
i++;j++;
}
else {
j = next[j];
}
}
if(j == needle.length()) return i - j;
else return -1;
}
};