This problem can be solved using KMP table by O(n).
idea
if the string has repeated pattern, then it must has a common prefix and suffix. that is the same thing when we implement KMP.
Then we will first calculated the longest common-fix table.
Then we can judge by:
common != 0 && len % (len - common) == 0;
code
public class Solution{
public boolean repeatedSubstringPattern(String str) {
int len = str.length();
if(len == 0)return true;
int[] table = presuf(str);
int common = table[len - 1];
return common != 0 && len % (len - common) == 0;
}
public int[] presuf(String s){
int len = s.length();
int[] table = new int[len];
if(len == 0)return table;
for(int i = 1; i < len; i++){
int last = table[i - 1];
while(true){
if(s.charAt(i) == s.charAt(last)){
table[i] = last + 1;
break;
} else {
if(last == 0)break;
last = table[last - 1];
}
}
}
return table;
}
}
