KMP-重复子字符串

Problem: 459. 重复的子字符串

题目

给定一个字符串str1, 判断其是否由重复的子串构成。

例子1：输入 str1=‘ababab’ ；输出 true
例子2：输入 str1=‘ababac’ ；输出 false

思路

重复子字符串组成的字符串，其肯定存在一个后缀和前缀是一样的，并且这个后缀其由后缀前面的字符子串组成。所以可以用前缀数组，先找到每个位置的最长相等前缀后缀，若最后一个字符的最长相等前缀后缀值不为零且最长后缀前的字符串长度被原字符串长度整除，那代表该最长后缀就是由前面的字符子串组成，即原字符串也由前面的字符子串组成。

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(n)$

Code

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        def get_next(str1):
            n = len(str1)
            pres = [-1] * (n +1)
            for i in range(n):
                t = pres[i]
                while str1[i] != str1[t] and t!=-1:
                    t = pres[t]
                pres[i+1] = t + 1 
            return pres[1:]
        pres = get_next(s)
        if pres[-1] and len(s) % (len(s)-pres[-1])==0:
            return True
        return False