网站建设千套素材,服装店的营销方法,东莞微网站建设,武鸣网站建设文章目录 习题28.找出字符串中第一个匹配项的下标1392.最长快乐前缀 本博客充分参考灵神和知乎的另一位博主 灵神KMP算法模版 知乎博主通俗易懂讲解
对于给定一个主串S和一个模式串P,如果让你求解出模式串P在主串S中匹配的情况下的所有的开始下标简单的做法又称为Brute-Force算… 文章目录 习题28.找出字符串中第一个匹配项的下标1392.最长快乐前缀 本博客充分参考灵神和知乎的另一位博主 灵神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
