# [LeetCode] #459. Repeated Substring Pattern

Environment: Python 3.7

Key technique: next function and KMP (**Knuth-Morris-Pratt) **method

**Example 1:**

**Input:** "abab"

**Output:** True

**Explanation:** It's the substring "ab" twice.

**Example 2:**

**Input:** "aba"

**Output:** False

**Example 3:**

**Input:** "abcabcabcabc"

**Output:** True

**Explanation:** It's the substring "abc" four times. (And the substring "abcabc" twice.)

**Analysis:**

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.

**Solution:**

`class Solution:`

def repeatedSubstringPattern(self, s: str) -> bool:

size = len(s)

next = [0] * 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

**Submitted result:**

**Lesson learn:**

The while loop is that I don’t consider in my code. It let me get many wrong answer. The str[7] is b and str[3] is c. We need move left one step to search and the the next[7] is 2 and while loop can execute this action.

<Find error and PMT[6] is 3 which means match aba)

<move left step and find PMT[7] is 2 which is match ab>

**Reference:**