class Solution(object): def repeatedSubstringPattern(self, str): """ :type str: str :rtype: bool """ def computeLPS(str): lps=*len(str) i=1 length=0 while i<len(str): if str[i]==str[length]: length+=1 lps[i]=length i+=1 else: if length: length=lps[length-1] else: lps[i]=0 i+=1 return lps lps = computeLPS(str) n = len(str) lenn = lps[-1] if lenn and n%(n-lenn)==0: return True else: return False
@protein.graph I'm comfused about your method . Could you please explain it? thanks
Sorry for late reply,
But you could do these steps to get an intuition.
Understand what computing LPS means, KMP algorithm
In short, it gives the proper longest prefix of string which is also a proper suffix.
For example, "bcabca" = [0,0,0,1,2,3] and "bcabc" = [0,0,0,1,2]
Now, if length of string is N, and we find LPS[-1] = L,
In order to check if the string is periodic, that is string is obtained by repeated substrings,
we need to check, N>0 and N%(N-L) == 0.