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 0n, m = len(haystack), len(needle)Next = self.generateNext(needle)j = 0for i in range(n):while haystack[i] != needle[j] and j > 0:j = Next[j - 1]if haystack[i] == needle[j]:j += 1if j == m:return i - j + 1return -1def generateNext(self, needle: str):m = len(needle)Next = [0 for _ in range(m)]left = 0for right in range(1, m):while needle[left] != needle[right] and left > 0:left = Next[left - 1]if needle[left] == needle[right]:left += 1Next[right] = leftreturn Next

459. 重復的子字符串

class Solution:def repeatedSubstringPattern(self, s: str) -> bool:size = len(s)if size == 0:return FalseNext = self.generateNext(s)if Next[size - 1] != 0 and size % (size - Next[size - 1]) == 0:return Truereturn Falsedef generateNext(self, p: str):m = len(p)Next = [0 for _ in range(m)]left = 0for right in range(1, m):while p[left] != p[right] and left > 0:left = Next[left - 1]if p[left] == p[right]:left += 1Next[right] = leftreturn Next

把整個字符串（長度為 size）當作是 KMP 算法中的模式串（needle），對其生成 Next 數組。如果字符串是由 n 個重復子串構成的，則 Next [size - 1] 一定是記錄了 n - 1 個子串的長度，即最長的相同前后綴長度為 n - 1 個子串長度。這樣 (size - Next[size - 1]) 就是單個子串的長度，如果 size % (size - Next[size - 1]) == 0，就說明這個字符串是由多個重復子串構成的。

總結

以上是生活随笔為你收集整理的字符串匹配经典题目——KMP算法（Leetcode题解-Python语言）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。