KMP算法和BM算法

KMP是前缀匹配和BM后缀匹配的经典算法。可以看出，前缀匹配和后缀匹配的区别只在于比较的顺序不同

前缀匹配是指模式串和母串的比较是从左到右，模式串的移动也是从左到右

后缀匹配是指模式串和母串从右向左的比较，模式串从左向右的移动。

通过前面的章节，很明显BF算法也是前缀算法，但是为了一一匹配的效率，自然没有必要提到O(mn)。KMP跟蛋疼在网上是有很多解释的，而且基本上是高个路线见你。我也很困惑，我试着用我自己的理解用最基础的方式来描述它

KMP

KMP也是一个优化的前缀算法。之所以被称为KMP，是因为它是克努特、莫里斯和普拉特的缩写。与BF相比，KMP算法的优化点在于“每次移动的距离”。它会动态调整每个图案串的移动距离。每次BF都是1。

KMP不一定

如图BF和KMP预算法所示，比较了两者的差异

我比较了这些图片，发现：

在文本串t中搜索模式串p，自然匹配第6个字母c时发现二级不一致。那么BF的方法是将整个模式串p移动一位，将KMP移动两位。

我们知道BF的匹配方法，但是为什么KMP移动两位数而不是一、三、四位呢？

上图我们解释过，模式串P匹配亚的斯亚贝巴是正确的，但是到了c就错了，那么KMP算法的思路就是：亚的斯亚贝巴是匹配完成的正确信息，我们能不能利用这个信息，不要把‘搜索位置’移回到被比较的位置，继续向后移动，从而提高效率。

那么问题来了，我怎么知道要移动多少位置？

这个偏移算法的作者KMP给我们总结了一下：复制代码如下：个移动数字=匹配字符-对应的部分匹配值偏移算法只和子串有关，没有文本串就没有羊毛关系，这里要特别注意

那么如何理解子串中匹配字符的个数以及对应的部分匹配值呢？

匹配字符：复制的代码代码如下：t 3360 ababababp : ababacabp，其中红色标记为匹配字符，易于理解。

部分匹配值：

这是核心算法，也很难理解

If:复制代码如下：t: aaronaabbccp: aaronaac，我们可以观察这个文本。如果我们在匹配c的时候犯了一个错误，就之前的结构而言，下一个最合理的移动位置是哪里？副本代码如下：aaronaabbcc aaronaac

也就是说，在模式文本中，某一段文字的头部和尾部是一样的，所以自然过滤的时候可以跳过这一段，这个思路也是有道理的

知道了这个规则，给定的部分匹配表的算法如下：

首先，我们应该理解两个概念：“前缀”和“后缀”。“前缀”指除最后一个字符以外的字符串的所有标题组合；“后缀”是指除第一个字符以外的字符串的所有尾部组合。

“部分匹配值”是“前缀”和“后缀”的最长公共元素的长度

让我们看看阿罗纳克的。如果是BF匹配，划分是这样的

BF的位移是：A，AA，AAR，AARO，AARON，AARONA，AARONAAC

KMP分部怎么样？这里将介绍前缀和后缀

我们先来看看KMP部分匹配表的结果如下：复制代码如下： A R O N A A C [0，1，0，0，1，2，0]

肯定是混淆了。我们不需要分解它。前缀和后缀复制代码如下：匹配字符串：“Aaron”前缀：a，Aa，Aar，Aaro后缀：aron，ron，on，n移动位置：其实就是比较每个匹配字符的前缀和后缀，然后计算共同长度

部分匹配表的分解

KMP的匹配表算法，其中p代表前缀，n代表后缀，r代表结果。复制代码如下：a，p=0，n=0，r=0

aa，p=[a]，n=[a]，r=a.length=1

aar，p=[a，aa]，n=[r，ar]，r=0

aaro，p=[a，aa，aar]，n=[o，ra，aro]，r=0

aaron p=[a，aa，aar，aaro]，n=[n，on，ron，aron]，r=0

aarona，p=[a，aa，aar，aaro，aaron]，n=[a，na，ona，rona，arona]，r=a.lenght=1

aaronaa，p=[a，aa，aar，aaro，aaron，aarona]，n=[a，aa，naa，onaa，ronaa，arona]，r=Math.max(a.length，aa.length)=2

aaronaac p=[a，aa，aar，aaro，aaron，aarona]，n=[c，ac，aac，naac，onaac，ronaac] r=0

类似于BF算法，先分解每次可能匹配的下标位置，先缓存。匹配时，使用这个《部分匹配表》来定位以后需要移动的位数

所以阿罗纳克匹配表的结果是0，1，0，0，0，1，2，0

下面将实现JS版的KMP，有两种

KMP (1)的实现：缓存匹配表的KMP

KMP实现(2):下一个KMP的动态计算

KMP执行情况(一)

匹配表

KMP算法中最重要的是匹配表。如果不匹配表，就是BF的实现，如果加上匹配表，就是KMP

匹配投票决定下一个位移的计数

根据上述匹配表的规则，我们设计了一个kmpGetStrPartMatchValue方法

函数kmpGetStrPartMatchValue(str){ var prefix=[]；var后缀=[]；var partMatch=[]；for (var i=0，j=str.lengthI j；i ) { var newStr=str.substring(0，I ^ 1)；if(NewStr . length==1){ PartMatch[I]=0；} else { for(var k=0；k I；K) {//前缀prefix[k]=newStr.slice(0，k ^ 1)；//后缀后缀[k]=NewStr . slice(-k-1)；//如果它们相等，则计算大小并将其放入结果集if(前缀[k]==后缀[k]) {partmatch [I]=前缀[k]。长度；} } if(！part match[I]){ part match[I]=0；} } }返回零件匹配；}

完全按照匹配表算法在KMP的实现，a-aa-AAR-AARO-AARONA-AARONA-AARONAAC用str.substring(0，I ^ 1)分解

然后在每次分解中通过前缀和后缀计算公共元素的长度

反推算法

KMP也是一个前置算法，可以完全移动BF。唯一的修改是BF在回溯时直接加1。当KMP回溯时，我们可以通过匹配表计算这个下一个值

//子循环for(var j=0；j searchLengthJ) {//如果与主字符串匹配，则为if (searchstr。charat (j)==sourcestr。charat(I)){//如果匹配，If(j==search length-1){ result=I-j；打破；} else {//如果匹配，继续循环，I用于增加主字符串的下标位I；}} else {//I在子串匹配中叠加if(j1part[j-1]0){ I=(I-j-part[j-1])；} else {//移动一位I=(I-j)} break；}}用红色标注的是next的值，KMP的核心点=匹配字符数-对应的部分匹配值

完全KMP算法

！doctype html div id=' test2 ' div脚本类型=' text/JavaScript '函数kmpGetStrPartMatchValue(str){ var prefix=[]；定义变量后缀=[];var partMatch=[]；for (var i=0，j=str.lengthI ji ) { var newStr=str.substring(0，I ^ 1)；if(NewStr。长度==1){ PartMatch[I]=0；} else { for(var k=0；k I；k ) { //取前缀前缀[k]=newStr.slice(0，k ^ 1)；后缀[k]=NewStr。切片(-k-1)；如果(前缀[k]==后缀[k]) { partMatch[i]=前缀k .长度；} } if(！零件匹配[I]){零件匹配[I]=0；} } }返回零件匹配；}函数KMP(sourceStr，searchStr) { //生成匹配表var part=kmpGetStrPartMatchValue(搜索字符串)；可变源长度=源字符串。长度；var搜索长度=搜索字符串。长度；定义变量结果；var I=0；var j=0；for(；I源字符串。长度；i ) { //最外层循环，主串//子循环for(var j=0；j searchLengthj ) { //如果与主串匹配if(搜索字符串。charat(j)==源字符串。charat(I)){//如果是匹配完成if(j==搜索长度-1){ result=I-j；打破；} else { //如果匹配到了，就继续循环，我是用来增加主串的下标位我；} } else { //在子串的匹配中我是被叠加了if (j 1部分[j - 1] 0) { i=(i - j -部分[j-1])；} else { //移动一位I=(I-j)} break；} } if(result | | result==0){ break；} } if(result | | result==0){ return result } else { return-1；} } var s=' BBC ABCDAB ABCDABDEvar t=' ABCDABDshow('indexOf '，function(){ return s . indexOf(t)})show(' KMP '，function() { return KMP(s，t) }) function show(bf_name，fn){ var myDate=new Date()(var r=fn()；var div=文档。创建元素(' div ')div。' innerhtml=BF _ name '算法，搜索位置：' r '，耗时（新日期()-我的日期)'毫秒；document.getElementById('test2 ').appendChild(div)；}/script/div/divKMP(二)

第一种kmp的算法很明显，是通过缓存查找匹配表也就是常见的空间换时间了。那么另一种就是时时查找的算法，通过传递一个具体的完成字符串，算出这个匹配值出来，原理都一样

生成缓存表的时候是整体全部算出来的，我们现在等于只要挑其中的一条就可以了，那么只要算法定位到当然的匹配即可

然后算法

函数next(str){ var prefix=[]；定义变量后缀=[];var partMatchvar I=str。长度变量newStr=str。子串(0，I ^ 1)；for(var k=0；k I；k ) { //取前缀前缀[k]=newStr.slice(0，k ^ 1)；后缀[k]=NewStr。切片(-k-1)；如果(前缀[k]==后缀[k]) { partMatch=前缀k .长度；} } if(！零件匹配){零件匹配=0；}返回partMatch}

其实跟匹配表是一样的，去掉了循环直接定位到当前已成功匹配的串了

完整的KMP.next算法

！doctype html div id=' test next ' div脚本类型=' text/JavaScript '函数next(str){ var prefix=[]；定义变量后缀=[];var partMatchvar I=str。长度变量newStr=str。子串(0，I ^ 1)；for(var k=0；k I；k ) { //取前缀前缀[k]=newStr.slice(0，k ^ 1)；后缀[k]=NewStr。切片(-k-1)；如果(前缀[k]==后缀[k]) { partMatch=前缀k .长度；} } if(！零件匹配){零件匹配=0；}返回partMatch}函数KMP(源字符串，搜索字符串){变量源长度=源字符串。长度；var搜索长度=搜索字符串。长度；定义变量结果；var I=0；var j=0；for(；I源字符串。长度；i ) { //最外层循环，主串//子循环for(var j=0；j searchLengthj ) { //如果与主串匹配if(搜索字符串。charat(j)==源字符串。charat(I)){//如果是匹配完成if(j==搜索长度-1){ result=I-j；打破；} else { //如果匹配到了，就继续循环，我是用来增加主串的下标位我；} } else { if(j ^ 1){ I=I-next(搜索字符串。切片(0，j))；} else { //移动一位I=(I-j)} break；} } if(result | | result==0){ break；} } if(result | | result==0){ return result } else { return-1；} } var s=' BBC ABCDAB ABCDABDEvar t=' ABCDABshow('indexOf '，function(){ returns . indexOf(t)})show(' KMP。next '，function() { return KMP(s，t) }) function show(bf_name，fn){ var myDate=new Date()(var r=fn()；var div=文档。创建元素(' div ')div。' innerhtml=BF _ name '算法，搜索位置：' r '，耗时（新日期()-我的日期)'毫秒；文件。getelementbyid(' testnext ').appendChild(div)；}/脚本/div/div

饭桶代码下载： https://github.com/JsAaron/data_structure