字符串匹配 之 KMP算法

本博客充分参考灵神和知乎的另一位博主

灵神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 ""