本系列是代码随想录算法训练营的学习笔记之day10，主要记录一下刷题的过程，以及核心知识点和一些值的记录的问题。

代码随想录的资源可以看参考链接【1】。

今日知识点

字符串基础：

• 字符串也是一种数组，在内存上连续分布；

今日题目

1. 重复的子字符串（459）

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

• 按照正常的思路来想可能就是用KMP算法，但是那个对于新手来说确实有点难懂；
• 在leetcode上看到另外一种思路，感觉太精彩了，那就是如果不可以由该字符串的子串构成，那么拼接两个相同的s，然后用自带的find函数去查找第二个s的起始下标，则下标应该等于len(s);

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        return (s + s).find(s, 1) != len(s)

• 用一行代码就巧解了这个题目，大佬们确实太强了！
• find(s,1)相当于删除了首字母，这样就不会匹配到第一个原始字符串s了；
• 如果s可以由子字符串subs组成，则s是有n个subs组成的，s+s就是由2n个subs组成，删除了首字母之后，n个subs组成的子字符串起始位置就只能向后滑动一个subs的长度了！这个思路太强。

KMP的代码如下：

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:  
        if len(s) == 0:
            return False
        nxt = [0] * len(s)
        self.getNext(nxt, s)
        if nxt[-1] != 0 and len(s) % (len(s) - nxt[-1]) == 0:
            return True
        return False
    
    def getNext(self, nxt, s):
        nxt[0] = 0
        j = 0
        for i in range(1, len(s)):
            while j > 0 and s[i] != s[j]:
                j = nxt[j - 1]
            if s[i] == s[j]:
                j += 1
            nxt[i] = j
        return nxt

• 从长远来说还是要掌握KMP算法，是这类题目的通用解法！

补充知识点

1. find函数的用法

str.find(str, beg=0, end=len(string))

用于在指定索引范围内查找是否包含子字符串str。

参考

【1】代码随想录：https://programmercarl.com/
【2】https://www.bilibili.com/video/BV1PD4y1o7nd/
【3】https://www.bilibili.com/video/BV1M5411j7Xx/