描述
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s = “abab”
输出: true
解释: 可由子串 “ab” 重复两次构成。
示例 2:输入: s = “aba”
输出: false
示例 3:输入: s = “abcabcabcabc”
输出: true
解释: 可由子串 “abc” 重复四次构成。 (或子串 “abcabc” 重复两次构成。)提示：
1 <= s.length <= 104
s 由小写英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/repeated-substring-pattern
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
法一：移动匹配
既然前面有相同的子串，后面有相同的子串，用 s + s，这样组成的字符串中，后面的子串做前串，前后的子串做后串，就一定还能组成一个s。所以判断字符串s是否由重复子串组成，只要两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成。
当然，我们在判断 s + s 拼接的字符串里是否出现一个s的的时候，要刨除 s + s 的首字符和尾字符，这样避免在s+s中搜索出原来的s，我们要搜索的是中间拼接出来的s。
class Solution {
public:
bool repeatedSubstringPattern(string s) {
string t = s + s;
// 掐头去尾
t.erase(t.begin());
t.erase(t.end()-1);
if(t.find(s) != std::string::npos)
return true;
return false;
}
};法二：KMP
假设字符串s使用多个重复子串构成（这个子串是最小重复单位），重复出现的子字符串长度是x，所以s是由n * x组成。
因为字符串s的最长相同前后缀的长度一定是不包含s本身，所以 最长相同前后缀长度必然是m * x，而且 n - m = 1，（这里如果不懂，看上面的推理）
所以如果 nx % (n - m)x = 0，就可以判定有重复出现的子字符串。
next 数组记录的就是最长相同前后缀， 如果 next[len - 1] != -1，则说明字符串有最长相同的前后缀（就是字符串里的前缀子串和后缀子串相同的最长长度）。
最长相等前后缀的长度为：next[len - 1] + 1。(这里的next数组是以统一减一的方式计算的，因此需要+1。
数组长度为：len。
如果len % (len - (next[len - 1] + 1)) == 0 ，则说明数组的长度正好可以被 (数组长度-最长相等前后缀的长度) 整除 ，说明该字符串有重复的子字符串。
数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。
// class Solution {
// public:
// bool repeatedSubstringPattern(string s) {
// string t = s + s;
// // 掐头去尾
// t.erase(t.begin());
// t.erase(t.end()-1);
// if(t.find(s) != std::string::npos)
// return true;
// return false;
// }
// };
class Solution {
public:
void getNext(int* next, string& s){
int j = -1;
next[0] = j;
for(int i=1; i<s.size(); i++){
while(j>=0 && s[i] != s[j+1])
j = next[j];
if(s[i] == s[j+1])
j++;
next[i] = j;
}
}
bool repeatedSubstringPattern(string s) {
int next[s.size()];
getNext(next, s);
int len = s.size();
// 这里的next数组是以统一减一的方式计算的，因此需要+1
if(next[len-1] != -1 && len % (len - (next[len-1] + 1)) == 0)
return true;
return false;
}
};
