Problem: 459. 重复的子字符串
题目
给定一个字符串str1, 判断其是否由重复的子串构成。
例子1：输入 str1=‘ababab’ ；输出 true
例子2：输入 str1=‘ababac’ ；输出 false
思路
重复子字符串组成的字符串，其肯定存在一个后缀和前缀是一样的，并且这个后缀其由后缀前面的字符子串组成。所以可以用前缀数组，先找到每个位置的最长相等前缀后缀，若最后一个字符的最长相等前缀后缀值不为零且最长后缀前的字符串长度被原字符串长度整除，那代表该最长后缀就是由前面的字符子串组成，即原字符串也由前面的字符子串组成。
复杂度
时间复杂度:
O ( n ) O(n) O(n)文章来源地址https://www.toymoban.com/news/detail-823187.html
空间复杂度:文章来源：https://www.toymoban.com/news/detail-823187.html
O ( n ) 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
到了这里，关于KMP-重复子字符串的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
