KMP 算法
KMP 算法
echobingo
发布于 2018-04-25 17:19:30
发布于 2018-04-25 17:19:30
题目描述：Leetcode 28. Implement strStr()
之前在 Leetcode 上 AC 的 O(MN) 版本：Q28 Implement strStr()
解题思路：
KMP 算法是经典的求解子串（模式串）出现在主串中位置的算法，也是数据结构当时学习的一个知识点。它因为在匹配过程中，主串下标不后退，而可以使时间复杂度从 O(MN) 降为 O(M+N) 。之前学过忘了，现在在此做一个总结。
KMP 算法的关键：求出子串（模式串）的 next 数组。
举例：
子串 pattern 下标 0 1 2 3 4 5 6 7 8 9 10 11 12
子串 pattern a b c d a z a a a b c a b
其对应的 next 数组为 0 0 0 0 1 0 1 1 1 2 3 1 2举例理解 next ：
第 2 个 ‘b’ 对应的 next9 = 2 ，其意义为从 ‘b’ 往前数，找到一个和从首字符开始相等的最长子串（‘ab’）。而第 2 个 ‘c’ 对应 next10 = 3，是因为从 ‘c’ 往前数，可以找到的与首字符开始数的相等的最长子串为 ‘abc’。其他同理。
如何求解 next 数组？
- 构造一个与子串长度相等大小的数组，初始化为 0；
- 还是以第 2 个 ‘b’ 对应的 next9 为例，next9 = 2 是怎么计算出来的呢？是因为前一个已经求得的 next8 = 1 对应的字符 pattern1 刚好也为 ‘b’ ，因此我们直接在 next8 = 1 基础上加1即可得到 next9 = 2；第 2 个 ‘c’ 对应 next10 = 3 的求解也是同理。
- next8 = 1 怎么求解呢？我们发现 next7 = 1对应的字符 pattern1 = ‘b’，不等于 ‘a’，此时我们将在 next[next7-1] 中继续找（这里是一个循环），发现 next0 = 0 对应的字符 pattern0 = ‘a’，这回相等了，我们就在 next0 = 0 基础上加1即可得到 next8 = 1。
- next2 = 0 怎么求解的呢？我们发现 next1 = 0 对应的字符 pattern0 = ‘a’，不等于 ‘c’，此时我们将在 next[next1-1] 中继续找（但是此时 next 下标已经小于0了，表明从最开始也没有找到匹配的最长子串），next2 直接赋为 0 即可。
- 循环一遍即可找到所有字符对应的 nexti 值。
如何利用 next 数组进行匹配？
简单来说，遍历主串，一个一个匹配，如果相等，主串和子串都向后移动一位，记录匹配的长度加 1；如果匹配失败，则主串的下标不变，子串的下标变为失配字符的前一个 next 数组的值，即 j = next[j-1]，同时，匹配的长度要更新为 j 而不是 0，因为前 j 个字符是匹配的。如果失配的字符下标 j = 0（下面例子的第四次匹配），说明从头都没有找到最长子串，这时主串的下标要加1，从下一个字符开始找，不然会陷入死循环。
可以结合下面这个例子理解上面这段话的匹配过程：
子串的下标 0 1 2 3 4 5 6 7 8 9
子串 pattern a b c d a a b c a b
子串的 next 数组 0 0 0 0 1 1 2 3 1 2
Python 实现：
class Solution:
# KMP 算法
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
# 边界情况处理
if len(needle) == 0:
return 0
if len(haystack) < len(needle):
return -1
# 产生 next 数组
next = self.nextArr(needle)
# print(next)
i = j = 0
length = 0
while i < len(haystack):
if haystack[i] != needle[j]:
if j == 0: # 到头还是无法匹配
i += 1
else:
j = next[j-1]
length = j # 已经比较过的长度
else:
length += 1
i += 1; j += 1
if length == len(needle):
return i - length
return -1 # 未找到
# 求 next 数组
def nextArr(self, needle):
lens = len(needle)
next = [0] * lens
for i in range(1, lens):
preNextVal = next[i-1]
while preNextVal > 0 and needle[i] != needle[preNextVal]:
preNextVal = next[preNextVal-1]
if needle[i] == needle[preNextVal]:
preNextVal += 1
next[i] = preNextVal
return next
# next 数组验证
print(Solution().nextArr('abcdazaaabcab')) # [0, 0, 0, 0, 1, 0, 1, 1, 1, 2, 3, 1, 2]
print(Solution().nextArr('abababzabababa')) # [0,0,1,2,3,4,0,1,2,3,4,5,6,5]
# 子串匹配 Test1
haystack = 'ababcdaabccabcdaabcab'
needle = 'abcdaabcab' # 对应的 next = [0, 0, 0, 0, 1, 1, 2, 3, 1, 2]
print(Solution().strStr(haystack, needle)) # 12
# 子串匹配 Test2
haystack = "ississip"
needle = "issip" # 对应的 next = [0,0,0,1,0]
print(Solution().strStr(haystack, needle)) # 3本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.03.19 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录