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

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。

“部门匹配”的实质（其实也就是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算法。

本文来源：开云网址-www.jiajiaobc.com