# [LeetCode] #459. Repeated Substring Pattern

Environment: Python 3.7

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

Example 1:

`Input: "abab"Output: TrueExplanation: It's the substring "ab" twice.`

Example 2:

`Input: "aba"Output: False`

Example 3:

`Input: "abcabcabcabc"Output: TrueExplanation: 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 =  * 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 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>

Reference: