KMP算法精解及其Python版的代码示例(kmp算法理解)

编辑：rootadmin

推荐整理分享KMP算法精解及其Python版的代码示例(kmp算法理解)，希望有所帮助，仅作参考，欢迎阅读内容。

文章相关热门搜索词:kmp算法理解,kmp算法 partial match table,kmp算法的概念,kmp算法 csdn,kmp算法简单例题,kmp算法 partial match table,kmp算法的概念,kmp算法 csdn,内容如对您有帮助，希望把文章链接给更多的朋友！

KMP算法是经典的字符串匹配算法，解决从字符串S，查找模式字符串M的问题。算法名称来源于发明者Knuth，Morris，Pratt。假定从字符串S中查找M，S的长度ls，M的长度lm，且（ls > lm）。

朴素的字符串查找方法从字符串S的第一个字符开始与M进行比较，如果匹配失败。从下一字符开始，重新比较。指导第 (ls - lm) 个字符。这种方法容易想到并且容易理解，效率不高。问题在于每次匹配失败后，移动的步伐固定为 1，其实步子可以迈得再大一些。

KMP的字符串查找方法假定在模式串的连续字串M[0, i] 且 i < lm，已经成功匹配字符串S。但是不巧第 i+1 个字符失败了，怎么办？移动一个字符，重头再来？当然不好，那就是朴素路线了。我们能否从跌倒的地方继续走呢？既然字串M[0 - i]已经匹配成功，那就从这个子串上做文章。举个栗子 S序号 j j + 1 j + 2 j + 3 j + 4 j + 5 j+6 j + 7 。。。 S串 a b c a b c d e 。。。 M串 a b c a b d

M序号

0 1 2 3 4 5 此时匹配失败在M串的第5个字符，前4个字符已经匹配成功。如果从跌倒的地方出发，则需要存在M[0, 4]的子串M[0, k] == S[j+4-k , j+4]。由于M[0, 4] == S[j , j+4] 则有字串S[j+4-k, j+4] == M[4-k, 4]。综上有M[0, k] == M[4-k, 4]如果这样的k不存在，那就老老实实的朴素了。从上面的表格可以直观的看出，下一次匹配只要把M串移动到 j + 3 位置，从 j+5 开始匹配就可以。很容易看出来在已经匹配成功的字串M[0 , 4]中有最长的子串（M[0 , 1] == M[3 , 4]），这个就是问题的关键。因此KMP的核心部分就是计算模式串的各个子串的 k。

实例首先我们来看一下字符串的朴素匹配.可以想象成把文本串s固定住,模式串p从s最左边开始对齐,如果对齐的部分完全一样,则匹配成功,失败则将模式串p整体往右移1位,继续检查对齐部分,如此反复.

关于kmp算法,讲的最好的当属阮一峰的<字符串匹配的KMP算法>.一路读下来,豁然开朗.其实就是,对模式串p进行预处理,得到前后缀的部分匹配表,使得我们可以借助已知信息,算出可以右移多少位.即 kmp = 朴素匹配 + 移动多位.更多细节请看阮一峰的文章,这里就不展开了.下面给出python的代码实现.

Python实现优先级队列结构的方法详解最简单的实现一个队列至少满足2个方法,put和get.借助最小堆来实现.这里按"值越大优先级越高"的顺序.#coding=utf-8fromheapqimportheappush,heappopclassPriorityQueue:def_

详解Python中的__new__、__init__、__call__三个特殊方法 __new__：对象的创建，是一个静态方法，第一个参数是cls。(想想也是，不可能是self，对象还没创建，哪来的self)__init__：对象的初始化，是一个实例方法

实例解析Python中的__new__特殊方法 __new__方法是什么？如果将类比喻为工厂，那么__init__()方法则是该工厂的生产工人，__init__()方法接受的初始化参数则是生产所需原料，__init__()方法会按