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.)

```

The thinking behind this problem is asa below:

1. The length of the repeating substring must be a divisor of the length of the input string
2. Search for all possible divisor of str.length, starting for length/2
3. If i is a divisor of length, repeat the substring from 0 to i the number of times i is contained in s.length
4. If the repeated substring is equals to the input str return true

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        char[] c = s.toCharArray();
        int n=s.length();
        for(int i=n/2-1;i>-1;i--){
            if(n%(i+1)==0) {
                int times = n/(i+1);
                StringBuilder sb = new StringBuilder();
                String sub = s.substring(0,i+1);
                while(times!=0){
                    sb.append(sub);
                    times--;
                }
                if(sb.toString().equals(s)) return true;
            }
        }
        return false;
    }
}

To optimize, you don’t have to construct a string from the substring, but compare the rest substrings to find all matches.

public boolean repeatedSubstringPattern(String str) {
        int len = str.length();
        for(int i=len/2 ; i>=1 ; i--) {
            if(len%i == 0) {
                int m = len/i;
                String subS = str.substring(0,i);
                int j;
                for(j=1;j<m;j++) {
                    if(!subS.equals(str.substring(j*i,i+j*i))) break;
                }
                if(j==m)
                    return true;
            }
        }
        return false;
    }