class Solution(object):
def repeatedSubstringPattern(self, str):
"""
:type str: str
:rtype: bool
"""
def computeLPS(str):
lps=[0]*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[length1]
else:
lps[i]=0
i+=1
return lps
lps = computeLPS(str)
n = len(str)
lenn = lps[1]
if lenn and n%(nlenn)==0:
return True
else:
return False
Python KMP O(n)



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%(NL) == 0.