[LeetCode] #459. Repeated Substring Pattern
Environment: Python 3.7
Key technique: next function and KMP (Knuth-Morris-Pratt) method
Explanation: It's the substring "ab" twice.
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)
Use KMP method to generate PMT. The manual result is as below for true case. The size in abab is 4 and the maximum number of PMT is 2. The true case (size) /(PMT) remainder should be zero.
def repeatedSubstringPattern(self, s: str) -> bool:
size = len(s)
next =  * size
for i in range(1, size):
k = next[i - 1]
while s[i] != s[k] and k :
k = next[k - 1]
if s[i] == s[k]:
next[i] = k + 1
p = next[-1]
return p > 0 and size % (size - p) == 0
The while loop is that I don’t consider in my code. It let me get many wrong answer. The str is b and str is c. We need move left one step to search and the the next is 2 and while loop can execute this action.
<Find error and PMT is 3 which means match aba)
<move left step and find PMT is 2 which is match ab>