LeetCode 459. 重复的子字符串

题目

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
例：
输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

方法一

若该字符串可以由一个字串重复多次构成，那么意味着我们可以通过对字符串的多次移位使其与原字符串相等
例：
原字符串：abcabc，该字符串由子串 abc 重复两次得到
第一次移位：cabcab
第二次移位：bcabca
第三次移位：abcabc
我们可以看到：第三次移位的结果与原字符串相等
根据该思路我们可以通过不断移位来判断，移位的次数为重复字符串的长度。但若重复字符串的长度过长，则导致程序运行时间过长
所以，我们可以通过创建新字符串来代替多次移位，该字符串为两个原字符串的相加
例：
新字符串：abcabcabcabc
该新字符串中包含了所有的移位情况：abcabc、cabcab 和 bcabca
由题可知，若原字符串可由子字符串重复 n 次可得，且 n≥2，那么新字符串则可由子字符串重复 2n 次可得。若我们将新字符串的首位两个字符去掉，此时新字符串可由子字符串重复 2n-2 次得到，且 2n-2≥n，即新字符串中一定包含源字符串

class Solution(object):
    def repeatedSubstringPattern(self, s):
        return True if s in (s + s)[1:-1] else False

方法二：KMP

构造 next 数组
若 next 数组的末尾的数值不为 -1，那么表示该字符串存在相同的前后缀，该值为最长相同前后缀的长度。同时，当字符串的长度除以字符串的长度与该字符串的最长相同前后缀的长度的差没有产生余数时，那么该字符串可以由一个字串重复多次构成
例：
存在字符串 asdfasdfasdf，判断是否存在子串可以重复多次构成该字符串

由 next 数组可知，next[11] = 7 ≠ -1，则该字符串存在相同前后缀，且其最长相同前后缀的长度为 next[11] + 1 = 8。因为 12 / (12 - 8) = 3，所以可以得出存在可以重复多次的子字符串

class Solution(object):
    def repeatedSubstringPattern(self, s):
        next = ['' for i in range(len(s))]
        self.getnext(next, s)
        if next[-1] != -1 and len(s) % (len(s) - (next[-1] + 1)) == 0:
            return True
        return False

    def getnext(self, next, s):
        j = -1
        next[0] = j
        for i in range(1, len(s)):
            while j > -1 and s[j+1] != s[i]:
                j = next[j]
            if s[j+1] == s[i]:
                j += 1
            next[i] = j
        return next

参考

方法一：https://leetcode.cn/problems/repeated-substring-pattern/solution/jian-dan-ming-liao-guan-yu-javaliang-xing-dai-ma-s/
方法二：https://programmercarl.com/0459.%E9%87%8D%E5%A4%8D%E7%9A%84%E5%AD%90%E5%AD%97%E7%AC%A6%E4%B8%B2.html

最后编辑于：2022.06.06 08:17:27