[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:

https://www.itread01.com/content/1522133891.html