Problem: 459. 重復(fù)的子字符串
題目
給定一個(gè)字符串str1, 判斷其是否由重復(fù)的子串構(gòu)成。
例子1：輸入 str1=‘a(chǎn)babab’ ；輸出 true
例子2：輸入 str1=‘a(chǎn)babac’ ；輸出 false
思路
重復(fù)子字符串組成的字符串，其肯定存在一個(gè)后綴和前綴是一樣的，并且這個(gè)后綴其由后綴前面的字符子串組成。所以可以用前綴數(shù)組，先找到每個(gè)位置的最長相等前綴后綴，若最后一個(gè)字符的最長相等前綴后綴值不為零且最長后綴前的字符串長度被原字符串長度整除，那代表該最長后綴就是由前面的字符子串組成，即原字符串也由前面的字符子串組成。
復(fù)雜度
時(shí)間復(fù)雜度:
O ( n ) O(n) O(n)文章來源地址http://www.zghlxwxcb.cn/news/detail-823187.html
空間復(fù)雜度:文章來源：http://www.zghlxwxcb.cn/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
到了這里，關(guān)于KMP-重復(fù)子字符串的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
