【力扣刷题】459.重复的子字符串-KMP

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

• 1 <= s.length <= 104
• s 由小写英文字母组成

充分性证明

如果一个字符串s是由重复子串组成，那么 最长相等前后缀不包含的子串一定是字符串s的最小重复子串。

如果s 是由最小重复子串p组成，即 s = n * p

那么相同前后缀可以是这样：

也可以是这样：

最长的相等前后缀，也就是这样：

这里有录友就想：如果字符串s 是由最小重复子串p组成，最长相等前后缀就不能更长一些？ 例如这样：

如果这样的话，因为前后缀要相同，所以 p2 = p1，p3 = p2，如图：

p2 = p1，p3 = p2 即： p1 = p2 = p3

说明 p = p1 * 3。

这样p 就不是最小重复子串了，不符合我们定义的条件。

所以，如果这个字符串s是由重复子串组成，那么最长相等前后缀不包含的子串是字符串s的最小重复子串。

#必要性证明

以上是充分性证明，以下是必要性证明：

如果 最长相等前后缀不包含的子串是字符串s的最小重复子串， 那么字符串s一定由重复子串组成吗？

最长相等前后缀不包含的子串已经是字符串s的最小重复子串，那么字符串s一定由重复子串组成，这个不需要证明了。

关键是要证明：最长相等前后缀不包含的子串什么时候才是字符串s的最小重复子串呢。

情况一， 最长相等前后缀不包含的子串的长度 比 字符串s的一半的长度还大，那一定不是字符串s的重复子串，如图：

图中：前后缀不包含的子串的长度 大于 字符串s的长度的 二分之一

情况二，最长相等前后缀不包含的子串的长度 可以被 字符串s的长度整除，如图：

步骤一：因为 这是相等的前缀和后缀，t[0] 与 k[0]相同， t[1] 与 k[1]相同，所以 s[0] 一定和 s[2]相同，s[1] 一定和 s[3]相同，即：，s[0]s[1]与s[2]s[3]相同 。

步骤二： 因为在同一个字符串位置，所以 t[2] 与 k[0]相同，t[3] 与 k[1]相同。

步骤三： 因为 这是相等的前缀和后缀，t[2] 与 k[2]相同 ，t[3]与k[3] 相同，所以，s[2]一定和s[4]相同，s[3]一定和s[5]相同，即：s[2]s[3] 与 s[4]s[5]相同。

步骤四：循环往复。

所以字符串s，s[0]s[1]与s[2]s[3]相同， s[2]s[3] 与 s[4]s[5]相同，s[4]s[5] 与 s[6]s[7] 相同。

可以推出，在由重复子串组成的字符串中，最长相等前后缀不包含的子串就是最小重复子串。

即 s[0]s[1] 是最小重复子串

以上推导中，录友可能想，你怎么知道 s[0] 和 s[1] 就不相同呢？ s[0] 为什么就不能是最小重复子串。

如果 s[0] 和 s[1] 也相同，同时 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讲解 (opens new window)，再去回顾一下。

或者说，自己举个例子，aaaaaa，这个字符串，他的最长相等前后缀是什么？

同上以上推导，最长相等前后缀不包含的子串的长度只要被 字符串s的长度整除，最长相等前后缀不包含的子串一定是最小重复子串。

情况三，最长相等前后缀不包含的子串的长度 不被 字符串s的长度整除得情况，如图：

步骤一：因为 这是相等的前缀和后缀，t[0] 与 k[0]相同， t[1] 与 k[1]相同，t[2] 与 k[2]相同。

所以 s[0] 与 s[3]相同，s[1] 与 s[4]相同，s[2] 与s[5]，即：，s[0]s[1]与s[2]s[3]相同 。

步骤二： 因为在同一个字符串位置，所以 t[3] 与 k[0]相同，t[4] 与 k[1]相同。

步骤三： 因为 这是相等的前缀和后缀，t[3] 与 k[3]相同 ，t[4]与k[5] 相同，所以，s[3]一定和s[6]相同，s[4]一定和s[7]相同，即：s[3]s[4] 与 s[6]s[7]相同。

以上推导，可以得出 s[0],s[1],s[2] 与 s[3],s[4],s[5] 相同，s[3]s[4] 与 s[6]s[7]相同。

那么 最长相等前后缀不包含的子串的长度 不被 字符串s的长度整除 ，最长相等前后缀不包含的子串就不是s的重复子串

充分条件：如果字符串s是由重复子串组成，那么 最长相等前后缀不包含的子串 一定是 s的最小重复子串。

必要条件：如果字符串s的最长相等前后缀不包含的子串 是 s最小重复子串，那么 s是由重复子串组成。

在必要条件，这个是 显而易见的，都已经假设 最长相等前后缀不包含的子串 是 s的最小重复子串了，那s必然是重复子串。

关键是需要证明， 字符串s的最长相等前后缀不包含的子串 什么时候才是 s最小重复子串。

同上我们证明了，当 最长相等前后缀不包含的子串的长度 可以被 字符串s的长度整除，那么不包含的子串 就是s的最小重复子串。

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