这篇文章主要介绍了JavaScript中数据结构与算法(五)：经典KMP算法,本文详解了KMP算法的方方面在,需要的朋友可以参考下

　　KMP算法和BM算法

　　KMP是前缀匹配和BM后缀匹配的经典算法，看得出来前缀匹配和后缀匹配的区别就仅仅在于比较的顺序不同

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

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

　　通过上一章显而易见BF算法也是属于前缀的算法，不过就非常霸蛮的逐个匹配的效率自然不用提了O(mn)，网上蛋疼的KMP是讲解很多，基本都是走的高大上路线看的你也是一头雾水，我试图用自己的理解用最接地气的方式描述

　　KMP

　　KMP也是一种优化版的前缀算法，之所以叫KMP就是Knuth、Morris、Pratt三个人名的缩写，对比下BF那么KMP的算法的优化点就在“每次往后移动的距离”它会动态的调整每次模式串的移动距离，BF是每次都+1，

　　KMP则不一定

　　如图BF与KMP前置算法的区别对比

　　我通过图对比我们发现：

　　在文本串T中搜索模式串P，在自然匹配第6个字母c的时候发现二等不一致了，那么BF的方法，就是把整个模式串P移动一位，KMP则是移动二位.

　　BF的匹配方法我们是知道的，但是KMP为什么会移动二位，而不是一位或者三位四位呢?

　　这就上一张图我们讲解下，模式串P在匹配了ababa的时候都是正确的，当到c的时候才是错误，那么KMP算法的想法是：ababa是正确的匹配完成的信息，我们能不能利用这个信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。

　　那么问题来了, 我怎么知道要移动多少个位置?

　　这个偏移的算法KMP的作者们就给我们总结好了：

　　代码如下:

　　移动位数 = 已匹配的字符数 - 对应的部分匹配值

　　偏移算法只跟子串有关系，没文本串没毛线关系，所以这里需要特别注意了

　　那么我们怎么理解子串中已匹配的字符数与对应的部分匹配值?

　　已匹配的字符：

　　 代码如下:

　　T : abababaabab

　　p : ababacb

　　p中红色的标记就是已经匹配的字符，这个很好理解

　　部分匹配值：

　　这个就是核心的算法了，也是比较难于理解的

　　假如：

　　 代码如下:

　　T：aaronaabbcc

　　P：aaronaac

　　我们可以观察这个文本如果我们在匹配c的时候出错，我们下一个移动的位置就上个的结构来讲，移动到那里最合理?

　　 代码如下:

　　aaronaabbcc

　　aaronaac

　　那么就是说：在模式文本内部，某一段字符头尾都一样，那么自然过滤的时候可以跳过这一段内容了，这个思路也是合理的

　　知道了这个规律，那么给出来的部分匹配表算法如下：

　　首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合;"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

　　"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度”

　　我们看看aaronaac的如果是BF匹配的时候划分是这样的

　　BF的位移: a,aa,aar,aaro,aaron,aarona,aaronaa,aaronaac

　　那么KMP的划分呢?这里就要引入前缀与后缀了

　　我们先看看KMP部分匹配表的结果是这样的：

　　代码如下:

　　a a r o n a a c

　　[0, 1, 0, 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,aronaa] , 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算法一下，先分解每一次可能匹配的下标的位置先缓存起来，在匹配的时候通过这个《部分匹配表》来定位需要后移动的位数

　　所以最后aaronaac的匹配表的结果 0,1,0,0,0,1,2,0 就是这么来的

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

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

　　KMP实现(二)：动态计算next的KMP

　　KMP实现(一)

　　匹配表

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

　　匹配表决定了next下一个位移的计数

　　针对上面匹配表的规律，我们设计一个kmpGetStrPartMatchValue的方法

　　?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 function kmpGetStrPartMatchValue(str) { var prefix = []; var suffix = []; var partMatch = []; for (var i = 0, j = str.length; i < 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); //后缀 suffix[k] = newStr.slice(-k - 1); //如果相等就计算大小,并放入结果集中 if (prefix[k] == suffix[k]) { partMatch[i] = prefix[k].length; } } if (!partMatch[i]) { partMatch[i] = 0; } } } return partMatch; }

　　完全按照KMP中的匹配表的算法的实现，通过str.substring(0, i + 1) 分解a->aa->aar->aaro->aaron->aarona->aaronaa-aaronaac

　　然后在每一个分解中通过前缀后缀算出共有元素的长度

　　回退算法

　　KMP也是前置算法，完全可以把BF那一套搬过来，唯一修改的地方就是BF回溯的时候直接是加1，KMP在回溯的时候我们就通过匹配表算出这个next值即可

　　?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 //子循环 for (var j = 0; j < searchLength; j++) { //如果与主串匹配 if (searchStr.charAt(j) == sourceStr.charAt(i)) { //如果是匹配完成 if (j == searchLength - 1) { result = i - j; break; } else { //如果匹配到了，就继续循环，i++是用来增加主串的下标位 i++; } } else { //在子串的匹配中i是被叠加了 if (j > 1 && part[j - 1] > 0) { i += (i - j - part[j - 1]); } else { //移动一位 i = (i - j) } break; } }

　　红色标记的就是KMP的核心点 next的值 = 已匹配的字符数 - 对应的部分匹配值

　　完整的KMP算法

　　?

1 2