KMP中的最小循环节

首先对next数组的理解：表示模块串的以第个字符结尾的子串中，前缀和后缀相同的最长字符串长度为。那么可以得出模块串的最小循环节长度为。证明如下：

模板题：LeetCode459.重复的子字符串

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

思路：根据以上分析，若字符串可被多个子串重复构成，那么不为0，且。综上代码如下：

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        s = " " + s;
        int[] next = new int[n+1];
        for(int i = 2, j = 0; i <= n;i++) {
            while(j > 0 && s.charAt(i) != s.charAt(j+1)) {
                j = next[j];
            }
            if(s.charAt(i) == s.charAt(j+1)) {
                j++;
            }
            next[i] = j;
        }
        int t = n - next[n];
        return t < n && n % t == 0;
    }
}