Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1:

Input: "abab"

Output: True

Explanation: It's the substring "ab" twice.

Example 2:

Input: "aba"

Output: False

Example 3:

Input: "abcabcabcabc"

Output: True

Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)

Solution 1: 先把input string S + S，再舍弃第一个和最后一个字母，看这字符串是否包含S，如果是，说明repeat

explanation: If the string S has repeated block, it could be described in terms of pattern.
S = SpSp(For example,Shas two repeatable block at most)
If we repeat the string, thenSS=SpSpSpSp.
Destroying first and the last pattern by removing each character, we generate a newS2=SxSpSpSy. If the string has repeatable pattern inside,S2should have validSin its string.

类似地，Consider a stringS="helloworld". Now, given another stringT="lloworldhe", can we figure out ifTis a rotated version ofS? Yes, we can! We check ifSis a substring ofT+T

Solution 2: The length of the repeating substring must be a divisor of the length of the input string

1. Search for all possible divisor ofstr.length, starting forlength/2
2. Ifiis a divisor oflength, repeat the substring from0toi,the number of timesiis contained ins.length
3. If the repeated substring is equals to the inputstrreturntrue

public boolean repeatedSubstringPattern(String str) {
    int l = str.length();
    for(int i=l/2;i>=1;i--) {
        if(l%i==0) {
            int m = l/i;
            String subS = str.substring(0,i);
            StringBuilder sb = new StringBuilder();
            for(int j=0;j<m;j++) {
                sb.append(subS);
            }
            if(sb.toString().equals(str)) return true;
        }
    }
    return false;
}

.