1、

这道题如果用暴力方法直接在原来的字符串里面找，时间复杂度是 O(n^2)。

2、

使用 KMP 算法求出 next 数组，通过 next 数组找到 next 数组的最后一个元素的值 next[n-1]，如果这个字符串可以由它的一个重复子串重复多次构成，那么 next[n-1]必然不为 0， 并且字符串长度 n 减去 next[n-1] 的值可以整除 n，即 next[n-1]!=0 && n%(n-next[n-1])==0，我用的 next 数组是没有减 1 的版本。使用减去 1 的next数组，用来判断的表达式为 next[n-1]!=0 && n%(n-(next[n-1]+1))==0。

具体原理如下：s 的长度是 n，假设构成 s 的子串的长度是 x，m*x=n，m 是正整数，next数组的最后一个元素记录的是 s 的最长相等前后缀长度 y，n-y=x，问题转化为判断 m 是否为正整数，即判断 y!=0 && n%(n-y)==0 是否成立。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n=s.length();
        char[] chars=s.toCharArray();
        int[] next=new int[n];
        // 得到next数组
        for(int i=1, j=0; i<n; i++){
            while(j>0 && chars[i] != chars[j]){
                j=next[j-1];
            }
            if(chars[i]==chars[j]){
                ++j;
            }
            next[i]=j;
        }
        return next[n-1]!=0 && n%(n-next[n-1])==0;
    }
}