Python实现kmp算法.zip

kmp算法 KMP算法是什么？ 引用自百度百科： KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度 也就是说，KMP算法是用来解决字符串匹配问题的，从一个主字符串text中寻找一个子字符串(模式字符串)pattern，看这个子串是否在主串中，比如对于text='abaacababcac'和pattern='ababc'，子串是包含在主串中的，同时它在主串中的索引是5。 字符串匹配暴力法 一般的字符串匹配解法是将2个串的字符进行挨个比较，相当于是把每个字符都比较了一遍，这样是一定能得到结果的，不过显然这样操作导致的时间复杂度是 也就是2个字符串的长度之积，俗称暴力解法。