本博客充分參考靈神和知乎的另一位博主

靈神KMP算法模版
知乎博主通俗易懂講解

• 對于給定一個主串S和一個模式串P,如果讓你求解出模式串P在主串S中匹配的情況下的所有的開始下標
• 簡單的做法又稱為Brute-Force算法,其實總的來說就是，外層循環遍歷主串S,內存循環遍歷模式串P,逐個匹配，當出現匹配不成功的情況，外層循環回到開始匹配位置+1,內層循環直接返回位置0，可想而知，這個算法的時間復雜度是o(n*m)
• KMP算法的改進思路，就是比較的時候，肯定是一個個比較的，這個是不能改進的，主要是可以降低比較趟數！
  • 外層循環主串S不會退，只回退模式串P，并且模式串P回退的時候充分利用真前綴和真后綴的最大匹配的長度！

話不多說，大家可以看上面知乎的講解就可以啦！

KMP算法python 模版

模版解決的問題：在主串s中查找模式串p,返回所有成功匹配的位置

def kmp(s: str, p: str) -> List[int]:m = len(p)# next[i] 表示p[0] 到 p[i] 的真前綴和真后綴的最大匹配長度next = [0] * m# cnt 用于記錄當前模式串p的真前綴和真后綴的最大匹配長度cnt = 0for i in range(1, m):b = p[i]while cnt and p[cnt] != b:cnt = pi[cnt - 1]if p[cnt] == b:cnt += 1next[i] = cnt# 記錄答案pos = []# cnt 用于存儲主串s和模式串p的匹配長度cnt = 0for i, b in enumerate(text):# 不相等就讓模式串p回退while cnt and p[cnt] != b:cnt = next[cnt - 1]if p[cnt] == b:cnt += 1if cnt == len(p):pos.append(i - m + 1)# 注意這個cnt = next[cnt - 1]return pos

習題

28.找出字符串中第一個匹配項的下標

28.找出字符串中第一個匹配項的下標

• 典型的KMP算法的模版題目

class Solution:def strStr(self, haystack: str, needle: str) -> int:# KMP算法m = len(needle)next = [0]*m cnt = 0# 預處理next數組for i in range(1,m):b = needle[i]while cnt and needle[cnt] != b :cnt = next[cnt-1]if needle[cnt] == b:cnt += 1next[i] = cnt # 開始匹配cnt = 0 for i,b in enumerate(haystack):while cnt and needle[cnt] != b:cnt = next[cnt-1]if needle[cnt] == b:cnt += 1if cnt == m:return i - m + 1return -1

1392.最長快樂前綴

1392.最長快樂前綴

• 算法思路：直接使用KMP算法進行求解，最終的next[m-1]就是最大的長度

class Solution:def longestPrefix(self, s: str) -> str:# 這個就是knp算法的max(next)m = len(s)next = [0]*(m)cnt = 0 ans = 0for i in range(1,m):b = s[i]while cnt and s[cnt] != b:cnt = next[cnt-1]if s[cnt] == b:cnt += 1next[i] = cntreturn s[:next[m-1]] if next[m-1] > 0 else ""