力扣459. 重复的子字符串（kmp算法）

题目描述：

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

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"
输出: false

示例 3:

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

本篇文章是写给已经会kmp算法的读者的，如果还不太理解kmp算法，建议先看字符串之KMP算法-CSDN博客

本题拿到之后，很明显我们只要求出kmp数组就行，所以我第一次做题的时候，很高兴的去完成了kmp模板，最后判断条件，只要kmp[len-1] ! =0即可，但这样就会出错了，因为我们看case 2

aba的kmp[len-1]也不是0，但是不符合，所以我们需要再加一个限制条件，那就是len % (len - (kmp[len - 1] )) == 0

为什么呢？因为当一个字符串由重复子串组成的，最长相等前后缀不包含的子串就是最小重复子串。

那这又是为什么呢？因为比如字符串s    abababab，最长相等前后缀是ababab，s[0]s[1]与s[2]s[3]相同， s[2]s[3] 与 s[4]s[5]相同，s[4]s[5] 与 s[6]s[7] 相同。发现都相差的是最长相等前后缀不包含的子串

所以数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。

实在不理解的读者，可以将kmp数组都打印出来，看看规律就知道了

AC代码

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
         int kmp[s.size()+1];
         kmp[0]=0;
         for(int i=1,j=0;i<=s.size()-1;i++){
            while(j&&s[i]!=s[j]){
                j=kmp[j-1];
            }
            if(s[i]==s[j]){
                j++;
            }
           kmp[i]=j;
         }
         int len=s.size();
         if (kmp[len - 1] != 0 && len % (len - (kmp[len - 1] )) == 0) {
            return true;
        }
         return false;
    }
};