本文主要是介绍[算法入土之路]KMP算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特--莫里斯--普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。 --来自baike.so.com
注: 详细思想及概念请跳转 kmp算法_360百科 (so.com)
本文通过代码及详细注释的方法带你了解KMP算法的流程
class KMP:def __init__(self, base_str):self.base_str = base_str # 需要进行匹配字符串self.index_arr = [i - 1 for i in range(len(base_str))] # 初始化index数组self.get_next_arr() # 根据匹配字符串生成 index 数组def algorithm(self, src_str):if not (self.base_str or src_str or src_str <= self.base_str):'''需要匹配的字符串为空, 原始字符串为空, 原始字符串比需要匹配的字符串长度短显而易见 以上情况都为不可能匹配到所需要求故直接返回'''return -1cur_1 = 0 # 原始字符串游标cur_base = 0 # 匹配字符串游标while cur_base < len(self.base_str) and cur_1 < len(src_str):'''离开循环的两种途径:1 原始字符串游标越界2 匹配字符串游标越界'''if self.base_str[cur_base] == src_str[cur_1]:# (1) 如果原始字符游标和匹配字符游标所指的字符相同# 两游标共同向前走cur_base += 1cur_1 += 1elif self.index_arr[cur_base] != -1: # == cur_base != 0# (2)如果(1) 不成立 但 cur_base 指向的元素不是 0 号元素# 则可以通过index_arr 进行跳跃 -> 减少匹配次数cur_base = self.index_arr[cur_base]else:# 如果 (1)(2) 均不成立# 则代表 当前字符和匹配字符的第0号字符也不相同# 则原始字符游标指向下一个字符cur_1 += 1return cur_1 - cur_base if cur_base == len(self.base_str) else -1def get_next_arr(self):i = 2cur = 0while i < len(self.base_str): # 遍历基础数组if self.base_str[i - 1] == self.base_str[cur]:# 如果当前元素的前一个元素与游标所指的元素相同# 即 到游标出的前缀 与等长度的后缀相同cur += 1 # 游标指向下一个元素self.index_arr[i] = cur # 当前元素的最长相同前后缀长度为游标距离原点的长度i += 1 # 当前元素游标指向下一个元素elif cur > 0: # 如果当前元素的前一个元素与游标所指元素不同 且游标未指向第 0 号元素# 根据游标在index_arr数组的位置所指向的位置 跳转'''原理:找到游标处获得的前后缀相同的位置, 并指向相同前缀的下一个元素'''cur = self.index_arr[cur]else:'''如果cur指向了第0号元素且第0号元素也与当前元素的前一个元素不同, 则将当前元素的相同前后缀长度置为零'''self.index_arr[i] = 0i += 1这篇关于[算法入土之路]KMP算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
