public boolean repeatedSubstringPattern(String str) {
//This is the kmp issue
int[] prefix = kmp(str);
int len = prefix[str.length()1];
int n = str.length();
return (len > 0 && n%(nlen) == 0);
}
private int[] kmp(String s){
int len = s.length();
int[] res = new int[len];
char[] ch = s.toCharArray();
int i = 0, j = 1;
res[0] = 0;
while(i < ch.length && j < ch.length){
if(ch[j] == ch[i]){
res[j] = i+1;
i++;
j++;
}else{
if(i == 0){
res[j] = 0;
j++;
}else{
i = res[i1];
}
}
}
return res;
}
Java & O(n)


@chnsht Thanks for the awesome solution. Just wanted to know the significance of:
n%(nlen) == 0 ?

@aman13
Because in the prefix array, the number means longest prefix and also suffix. So
nlen: the length of prefix(should be the repeated sequence),
n%(nlen): check if the candidate sequence is the answer(if it is the answer, the array should not have remains). Hope this helps.


If anyone is stuck with understanding kmp, I found this explanation is pretty clear. Please check it out:
http://jakeboxer.com/blog/2009/12/13/theknuthmorrisprattalgorithminmyownwords/

excellent solution! Simulate KMP method!
public class Solution { public boolean repeatedSubstringPattern(String s) { int[] pre=kmp(s); int len=pre[pre.length1]; if(len>0&&pre.length%(pre.lengthlen)==0){ return true; } return false; } public int[] kmp(String s){ char[] array = s.toCharArray(); int i=0; int j=1; int[] pre=new int[array.length]; pre[0]=0; while(j<array.length){ if(array[i]==array[j]){ pre[j]=i+1; i++; j++; }else{ if(i!=0){ i=pre[i1]; }else{ pre[j]=0; j++; } } } return pre; } }

@bluecloud build kmp is O(n). i will increase at most n times and thus decrease at most n times and total is n+n=O(n)
you can find more detailed discussion below:
https://leetcode.com/problems/shortestpalindrome/solution/#approach3kmpaccepted




@chnsht Hi
Can you explain how did you determine that substring is 3 char long by subtracting
str.length()  Value at Last Index in Prefix []
I understood KMP logic first time but still unable to digest this idea of nlen in below line.
n%(nlen) == 0