KMP算法介绍

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。

暴力解法

目标串：ABACABAB

模式串：ABAB  

利用表格的形式，阐释暴力解法的思路，每次取目标串的一个字符与模式串的字符进行对一一对比，只要相等，则比较下一位。

若不相等，则从目标串的下一次位置开始。

代码如下，最容易让人理解的思路。但是空间复杂度为O(m*n).

def Brute_Force(target_str, model_str):""":param target_str:目标串 :param model_str: 模式串:return: 首次匹配位置"""target_len = len(target_str)model_len = len(model_str)# 循环次数为目标串长度-模式串长度for i in range(target_len - model_len + 1):# 变量K的作用，遍历模式串 k = 0for j in range(i, i + model_len):# print("i", i, "j", j, "target_str", target_str[j], "model_str", model_str[k])# 不匹配if target_str[j] != model_str[k]:breakelse:k += 1else:return i

改变版，匹配，减少循环次数，只使用一次循环。

def Brute_Force_upgrade(target_str, model_str):target_len = len(target_str)model_len = len(model_str)# 循环用上面代码中循环一样 for i in range(target_len - model_len + 1):# 比较字符时候，取同模式串长度一样的目标串# 满足输出首次匹配位置if target_str[i:i + model_len] == model_str:return i

KMP 算法，思路

未完待续...