[LeetCode] #459. Repeated Substring Pattern

Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.
Input: "aba"
Output: False
Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)
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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Fatboy Slim

Fatboy Slim

Interesting in any computer science.