字符串匹配经典题目——KMP算法（Leetcode题解-Python语言）

28. 实现 strStr()

strStr(haystack: str, needle: str) 的作用就是在 haystack 字符串（长度为 n）中找出 needle 字符串（长度为 m）出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 ；如果 needle 是空字符串，则返回 0。 Python 中对应的写法是 haystack.find(needle)。

如果让我们自己实现这个函数，最简单的思路就是对 haystack 字符串中每个字符的位置，都用 needle 字符串试着去匹配，这样的最坏时间复杂度是 O(n * m)。KMP 算法的思路是对 needle 字符串（即模式字符串）进行预处理，用一个 Next 数组（前缀表）记录下每个字符位置作为最后一个字符时，前后缀字符串相等的最大长度。当出现一个不匹配字符时，（needle 字符串中）它的前面如果有相同的前缀和后缀，则 needle 字符串可以跳到 haystack 字符串中对应后缀的位置开始匹配，而不是 haystack 字符串中后一位的位置。

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle:
            return 0
        n, m = len(haystack), len(needle)
        Next = self.generateNext(needle)
        j = 0
        for i in range(n):
            while haystack[i] != needle[j] and j > 0:
                j = Next[j - 1]
            if haystack[i] == needle[j]:
                j += 1
            if j == m:
                return i - j + 1
        return -1

    def generateNext(self, needle: str):
        m = len(needle)
        Next = [0 for _ in range(m)]
        left = 0
        for right in range(1, m):
            while needle[left] != needle[right] and left > 0:
                left = Next[left - 1]
            if needle[left] == needle[right]:
                left += 1
            Next[right] = left
        return Next

459. 重复的子字符串

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        size = len(s)
        if size == 0:
            return False
        Next = self.generateNext(s)
        if Next[size - 1] != 0 and size % (size - Next[size - 1]) == 0:
            return True
        return False

    def generateNext(self, p: str):
        m = len(p)
        Next = [0 for _ in range(m)]
        left = 0
        for right in range(1, m):
            while p[left] != p[right] and left > 0:
                left = Next[left - 1]
            if p[left] == p[right]:
                left += 1
            Next[right] = left
        return Next

把整个字符串（长度为 size）当作是 KMP 算法中的模式串（needle），对其生成 Next 数组。如果字符串是由 n 个重复子串构成的，则 Next [size - 1] 一定是记录了 n - 1 个子串的长度，即最长的相同前后缀长度为 n - 1 个子串长度。这样 (size - Next[size - 1]) 就是单个子串的长度，如果 size % (size - Next[size - 1]) == 0，就说明这个字符串是由多个重复子串构成的。