给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。
示例 1:
输入: "abab"
输出: True
解释: 可由子字符串 "ab" 重复两次构成。
示例 2:
输入: "aba"
输出: False
示例 3:
输入: "abcabcabcabc"
输出: True
解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        ...
    }
    public static void main(String[] args) {
        System.out.println(new Solution().repeatedSubstringPattern("aba"));
    }
}

核心点：一个子串重复多次构成、只含有小写英文字母、长度不超过10000
思路：
1、确定每次重复的个数，这是我们能够确定的。例如"abababab"，长度为8。那么每次重复个数情况有1、2、4。(for循环模一下即可判定)
2、直到重复个数之后就好办了，重新开个for循环从指定位置开始指定长度比较就ok，一旦一组比较下来都相同直接返回true，否则进行其他重复个数情况二次比较！

public boolean repeatedSubstringPattern(String s) {
    String subStr = "";
    for (int i = 1; i < s.length(); i++) {
        //每i个数能够成对出现
        if(s.length() % i == 0){
            subStr = s.substring(0,i);
            int j = i;
            for (; j < s.length(); j+=i) {
                if(!Objects.equals(subStr,s.substring(j,j+i))){
                    break;
                }
            }
            if(j == s.length()){
                return true;
            }
        }
    }
    return false;
}

注释的内容表示被替换了
public boolean repeatedSubstringPattern(String s) {
    //        String subStr = "";
    for (int i = 1; i < s.length(); i++) {
        if(s.length() % i == 0){
            //                subStr = s.substring(0,i);
            int j = i;
            for (; j < s.length(); j+=i) {
                //左右指针比较
                //                    if(!Objects.equals(subStr,s.substring(j,j+i))){
                //                        break;
                //                    }
                /*******直接取子串=>左右连续对比*******/
                int subStrCur = 0;
                int jCur = j;
                while(subStrCur != i){
                    if(s.charAt(subStrCur) != s.charAt(jCur)){
                        break;
                    }
                    subStrCur++;
                    jCur++;
                }
                if(subStrCur != i){
                    break;
                }
                /**************/
            }
            if(j == s.length()){
                return true;
            }
        }
    }
    return false;
}

举例：
例1：s="abababab"  next[] = [-1, -1, 0, 1, 2, 3, 4, 5]
  next数组最后一个位置为5，指向原字符串中的倒数第三个，使用原字符串长度减去该位置-1，8-5-1=2，2就指的是对应子串的长度，接着使用字符串长度进行%,若是=0，表示其为重复子串。公式为：s.length() % (s.length() - targetPos - 1) == 0
例2：s="ababcddc" next=[-1, -1, 0, 1, -1, -1, -1, -1]
  最后位置为-1，直接判定没有重复字符串。
例3：s="ababcdab" next[] = [-1, -1, 0, 1, -1, -1, 0, 1]
  最后位置为1，同理代入，8%(8-1-1)=2，没有整%，所以直接判断没有

public int getNext(String s) {
    //KMP求得next数组        
    int next[] = new int[s.length()];
    int j = -1;
    next[0] = -1;
    for (int i = 1; i < s.length(); 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;
    }
    return next[s.length() - 1];
}
public boolean repeatedSubstringPattern(String s) {
    //使用KMP取到最后一个元素重复元素前缀位置
    int targetPos = getNext(s);
    if (targetPos == -1) {
        return false;
    }
    if (s.length() % (s.length() - targetPos - 1) == 0) {
        return true;
    }
    return false;
}

假设某个字符串长度为8，按照正常思路顺序，先取最长重复串长度为4个4个比较、失败取2个2个、失败再取1个1个。
其实后面的两次就是没有必要的，我们举个例子："abababac"
  ①abab abac  (失败)
  ②ab ab ab ac (失败)
  ③a b a b a b b a c (失败)
仔细看第二步，假设它是重复串组成ab ab ab ab，那么就必然就有abab abab判断成功，那么①失败，下面的②③比较自然没有必要了。其规律就可以找到凡是某个最大子串匹配失败，那么其整除的情况(也就是②③)直接可以省略掉。
上面说明了没必要重复比较的情况，下面再举一个长度为6的例子："ababab"
  ①aba bab (失败)
  ②ab ab ab （成功）
对于该种情况，第②步是不用被省略的，因为第一组最大重复数量为3，其并不能整除2，那么对重复长度为2的自然会进行一一比较，这里就有一个问题，我们该如何进行比较？上面长度为6的有三组，难道要一个一个进行比？从大佬的代码中我又看到了解答，所有任意情况只要比较1次即可，对于②中取出abab abab这两个，刚开始我也贼蒙蔽，不过之后就感叹其妙的地方了。
重复长度2，第一组[0,6-2-1]=>[0,3] 第二组[2,6-1]=>[2-5],假设三组子字符串都先相同，那么任意两组之和也必然相同，借助这个要点，我们即可将多组比较化为2组比出结果。

public boolean repeatedSubstringPattern2(String s) {
    int len = s.length();
    int parts = 2;//从2开始，之后取子串len/2、len/3，保证子串从最大长度开始进行比较重复
    int noRepeatLen = len;
    while (noRepeatLen > 1) {
        if (noRepeatLen % parts == 0) {
            int k = len / parts;//子串长度
            //取出两组进行比较
            if (Objects.equals(s.substring(0, len - k), s.substring(k))) {
                return true;
            }
            //去除重复的整除情况，在除数上进行操作
            noRepeatLen /= parts;
            while (noRepeatLen % parts == 0) {
                noRepeatLen /= parts;
            }
        }
        parts++;
    }
    return false;
}

① s="abac" 不重复情况  "ababca"
 s+s = "abacabac"，去头去尾"bacaba"
② s="abab"
 s+s = "abababab"，去头去尾"bababa" √
③ s="aaaa"
 s+s = "aaaaaaaa"，去头去尾"aaaaaa" √
 这种方式很巧妙，通过拼接方式去头去尾看其中是否存在原字符串。若是有重复的必然拼接中有对应重复的！

public boolean repeatedSubstringPattern(String s) {
    String str = s + s;
    return str.substring(1, str.length() - 1).contains(s);
}