Betway88必威
Mou Mou Jidian Generator
发电机维修 发电机回收
发电机出售 发电机租赁
客户统一服务热线

0732-209002325
12425468388

您的位置: 主页 > 工程案例 > 酒店场所 >

LeetCode条记:字符串匹配——KMP算法

本文摘要:LeetCode第28题:实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串泛起的第一个位置 (从0开始)。如果不存在,则返回 -1。示例 1:输入: haystack = hello, needle = ll输出: 2示例 2:输入: haystack = aaaaa, needle = bba输出: -1说明:当 needle 是空字符串时,我们应当返回什么值呢?

Betway88必威

必威一betway088

LeetCode第28题:实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串泛起的第一个位置 (从0开始)。如果不存在,则返回 -1。示例 1:输入: haystack = "hello", needle = "ll"输出: 2示例 2:输入: haystack = "aaaaa", needle = "bba"输出: -1说明:当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。

对于本题而言,当 needle 是空字符串时我们应当返回 0。这与C语言的 strstr() 以及 Java的 indexOf() 界说相符。字符串匹配是盘算机的基本任务之一,有许多种算法,其中Knuth-Morris-Pratt算法(简称KMP)是常用的之一,思路比力庞大,以其三个发现者命名算法思路以文本串"BBC ABCDAB ABCDABCDABDE"和模式串"ABCDABD" 为例首先,文本串与模式串的第一个字符比力不匹配,所以文本串指针后移一位不匹配,文本串指针继续后移……直到模式串的第一个字符匹配乐成,双指针同时后移一位继续匹配乐成,双指针继续后移……至此匹配失败此时如果将文本串指针回退到下一个起始位置,并将模式串指针归零,那么就是暴力搜索算法,时间庞大度为O(n * m)(设文本串长度为n,模式串长度为m),较高KMP算法的思路是当匹配失败时,模式串指针前面的"AB"与模式串开头的"AB"是匹配的,使用这个信息,可以将模式串的指针从6回退到2,这里的从6到2的映射,需要事先盘算出来,也就是“模式串的部门匹配值”,这个我们后面再讲不匹配,凭据“模式串的部门匹配值”,模式串指针从2回退到0不匹配,由于模式串的指针在开头,因此文本串指针右移一位……不匹配,凭据“模式串的部门匹配值”,模式串指针从6回退到2……直至匹配乐成,算法竣事以上KMP算法的总体思路是:当匹配乐成时,双指针同时后移一位当匹配失败时,如果模式串指针为0,则文本串指针后移一位否则模式串指针凭据“模式串的部门匹配值”回退下面讲一下“模式串的部门匹配值”的盘算,这里我们界说字符串的:前缀:字符串的全部头部子串(不包罗自身)后缀:字符串的全部尾部子串(不包罗自身)模式串的部门匹配值,界说为一个i->j的映射,j为模式串前i位子串的前缀和后缀的最大相同长度以"ABCDABD"为例"A"的前缀和后缀都为空集,共有元素的长度为0;"AB"的前缀为["A"],后缀为["B"],共有元素的长度为0;"ABC"的前缀为["A", "AB"],后缀为["BC", "C"],共有元素的长度0;"ABCD"的前缀为["A", "AB", "ABC"],后缀为["BCD", "CD", "D"],共有元素的长度为0;"ABCDA"的前缀为["A", "AB", "ABC", "ABCD"],后缀为["BCDA", "CDA", "DA", "A"],共有元素为"A",长度为1;"ABCDAB"的前缀为["A", "AB", "ABC", "ABCD", "ABCDA"],后缀为["BCDAB", "CDAB", "DAB", "AB", "B"],共有元素为"AB",长度为2;"ABCDABD"的前缀为["A", "AB", "ABC", "ABCD", "ABCDA", "ABCDAB"],后缀为["BCDABD", "CDABD", "DABD", "ABD", "BD", "D"],共有元素的长度为0。

必威一betway088

“部门匹配”的实质(其实也就是KMP算法的本质)是,部门模式串的头部和尾部有时会重复,当模式串与文本串匹配失败时,模式串当前指针(例子中的"ABCDABD")的前面一部门("ABCDABD")与模式串的头部("ABCDABD")相同,使用这个信息,可以跳过一些文本串和模式串的指针,从而降低庞大度可是,根据上文形貌的盘算逻辑,盘算“模式串的部门匹配值”这个历程,时间庞大度是很高的O(m ^ 3),所以需要通过一些算法来降低庞大度,好比使用动态计划设模式串为s,界说“模式串的部门匹配值”为a[],给定初始值a[0] = 0在盘算a[i]时,令j = a[i - 1]凭据a[i - 1]的寄义,我们知道s[: i]中最长的相同前缀和后缀是s[: j]与s[i - j: i]比力s[i]和s[j],如果相同,那么这两个字符就可以划分加到上面的后缀和前缀中,成为s[: i + 1]中最长的相同前缀和后缀,长度为j + 1,即j = a[i - 1]if s[i] == s[j]: a[i] = j + 1如果s[i] != s[j],那么就需要寻找s[: i + 1]中短一点的相同前缀和后缀就是要寻找s[i - j: i]去掉头部一些元素,再加上s[i],能否与s的头部对上,这里需要视察到,由于s[: j] = s[i - j: i],所以上述问题等价于,s[: j]去掉头部一些元素,再加上s[i],能否与s的头部对上,s[: j]中最长的相同前缀和后缀,是s[: a[j - 1]]和s[j - a[j - 1]: j]因此只需要对比s[i]和s[a[j - 1]],这里就是动态计划递归发生的地方if s[i] != s[j]: j = a[j - 1]对j循环迭代,直至s[i]与s[j]匹配乐成或者j回退到0退出庞大度分析设文本串长度n,模式串长度m时间庞大度盘算“模式串部门匹配值”的历程盘算第i位需要O(m),即指针回退的最大步数,总共盘算m位时间庞大度为O(m ^ 2)匹配历程设文本串指针为i,模式串指针为j初始值i = 0,j = 0算法竣事的最差条件为i > n双指针共有三种移动类型:a:匹配乐成,i ++,j ++b:匹配失败且j = 0,i ++c:匹配失败且j != 0,j回退设每种移动类型的次数为f()a和b中i都是单向移动,所以f(a) + f(b) <= n这里我们构建一个虚拟的移动类型:d:匹配失败且j != 0,j --c中j回退到0的速度是大于即是d中j --到0的速度的,所以f(c) <= f(d)这里我们可以注意到,由于d的前置条件是j != 0,所以f(d) <= f(a)通俗明白就是,初始位置在0的j,右移的次数一定大于即是左移的次数综上f(a) + f(b) + f(c) <= f(a) + f(b) + f(d) <= f(a) + f(b) + f(a) <= 2(f(a) + f(b)) <= 2n时间庞大度为O(n)KMP算法总的时间庞大度为O(n + m ^ 2)空间庞大度“模式串部门匹配值”的效果需要维护一个长度为m的数组匹配历程需维护双指针+已匹配的字符数,共3个变量总的空间庞大度为O(m)代码(python3)class Solution: def strStr(self, haystack: str, needle: str) -> int: # 特殊情况 if len(needle) == 0: return 0 if len(haystack) == 0: return -1 return self.kmpMatch(haystack, needle) def kmpMatch(self, haystack, needle): ''' KMP算法 ''' result = -1 needle_partial_match = self.partialMatch(needle) # 双指针 i = 0 j = 0 # 已匹配的字符数 matched_count = 0 while i < len(haystack) and j < len(needle): # 双指针匹配,双指针同时右移一位 if haystack[i] == needle[j]: if j == len(needle) - 1: result = i - j return result i += 1 j += 1 matched_count += 1 continue # 双指针不匹配,且needle的指针是第0位,则haystask指针右移一位,已匹配的字符数更新为0 if j == 0: i += 1 matched_count = 0 continue # 双指针不匹配,且needle的指针不是第0位,则needle指针左移至(已匹配的字符数对应的部门匹配值)位置,已匹配的字符数更新为needle指针前面的位数 j = needle_partial_match[j - 1] matched_count = j return result def partialMatch(self, s): ''' 对于模式串,求出每一位的部门匹配值,即当匹配失败时,needle需要移动的位数 部门匹配值界说为:部门字符串的前缀和后缀相同的最大长度 使用动态计划降低庞大度 ''' result = [None] * len(s) # 界限条件 result[0] = 0 if len(s) == 1: return result for i in range(1, len(s)): result[i] = 0 j = result[i - 1] while j >= 0: if s[i] == s[j]: result[i] = j + 1 break if j == 0: break j = result[j - 1] return result参考文献阮一峰的网络日志:字符串匹配的KMP算法。


本文关键词:必威一betway088,LeetCode,条记,字符串,匹配,—,KMP,算法,LeetCode

本文来源:Betway88必威-www.cdyingli.com

Copyright © 2006-2021 www.cdyingli.com. Betway88必威科技 版权所有  ICP备案:ICP备17840740号-2