字符串匹配KMP算法 _KMP算法

什么是KMPKMP(D.E.Knuth,J.H.Morris,V.R.Prat)是三个发明者的名字首字母命名的。用于字符串匹配的经典算法。
常规匹配算法这个算法很抽象，研究了些时间才慢慢弄懂里面的一些奥秘之处，并借此记录下来，以便后期回顾。
常规字符串匹配方式：
主串:ABC ABCDAB ABCDABCDABDE
模式串:ABCDABD
【字符串匹配KMP算法】我们要在主串里查找匹配串是否存在，那么常规匹配方式如下：
主串和模式串都从头开始匹配，当出现不匹配的字符时，如图1所示，主串A字符和模式串的D字符不匹配，那么说明主串A开头和模式串不匹配，主串往后移从B字符开始重新和模式串进行比较(如图2) 。因为主串B和模式串A不相等，所以主串往后移继续和模式串比较(如图3),重复以上操作，知道在主串中找到对应的字串或者找不到。但是这样比较的效率十分低，当出现不相等就会对模式串复位，然后从头开始比较。要想比较速度加快，不用每次模式串都是从头开始比较，下面介绍的KMP算法，就可以做到。

文章插图
图1

文章插图
图2

文章插图
图3

KMP实现KMP的思想是当主串和模式串不相等时
1.主串不用像常规匹配那样，需要从上一次的下一个位置开始重新和模式串进行匹配，保持当前位置不变和已经移动过的模式串进行匹配,如果模式串移动的字符为0并且第一个字符和主串的当前字符也不相等，那么主串需要往后移动一个字符继续和模式串匹配。
2.模式串将已经对比过的好前缀一次性往后移动多个字符。
如图4，当主串的空格和模式串的D不相等时，主串位置保持不变，模式串不用从0下标开始，而是从下标2开始重新匹配。因为ABCDAB主串和模式中进行对比后是相等的，那么，坏字符D的最长前缀和后缀集合是AB，长度为2 。
模式串的起始位置依赖一张表叫部分匹配表。

文章插图
图4
部分匹配表：

文章插图
图5
部分匹配表是根据好前缀和好后缀共有元素的长度
A 前缀和后缀的集合为空共有元素长度为0
AB 前缀【A】,后缀【B】共有元素长度为0
ABC 前缀【A,AB】,后缀【BC, C】共有元素长度为0
ABCD 前缀【A,AB,ABC】,后缀【BCD,CD,D】共有元素长度为0
ABCDA 前缀【A,AB,ABC,ABCD】,后缀【BCDA,CDA,DA,A】共有元素长度为1
ABCDAB 前缀【A,AB,ABC,ABCDA】,后缀【BCDAB,CDAB,DAB,AB,B】共有元素长度为2
ABCDABD 前缀【A,AB,ABC,ABCDAB】,后缀【BCDABD,CDABD,DABD,ABD,BD,D】共有元素长度为0

在程序中部分匹配表可以使用一个数组来保存，可以命名为next数组，next数组的下标为当前正在和主串进行比较的字符下标，其值是当前字符的好前缀和好后缀共有元素的长度。
我们约定next[0]为-1，那么上面的部分匹配转换成next数组如下：
next[0]=-1 A A字符的好前缀和好后缀共有元素长度为0
next[1]=0 AB B字符的好前缀和好后缀共有元素长度为0
next[2]=0 ABC C字符的好前缀和好后缀共有元素长度为0
next[3]=0 ABCD D字符的好前缀和好后缀共有元素长度为0
next[4]=1 ABCDA A字符的好前缀和好后缀共有元素长度为1
next[5]=2 ABCDAB B字符的好前缀和好后缀共有元素长度为2
next[6]=0 ABCDABD D字符的好前缀和好后缀共有元素长度为0

代码实现：

//s:模式串len:模式串长度next:next数组保存部分匹配表数据void getNext(char *s, int len, int *next){int k = -1; //模式串s下标j的前后缀共有元素长度int j = 0;//模式串的下标next[0] = -1;//第一个元素的共有元素约定为-1while(j < len){if(k == -1 || s[k] == s[j]){//k=-1表示是第一个字符//如果前缀和后缀有共有元素，那么前缀和后缀都后移一个字符，然后再次比较 。k++;j++;next[j] = k; //将当前字符的前缀和后缀共有元素长度保存到next数组}else{k = next[k]; //如果不等，那么前缀字符串根据next数组往前查找和当前字符为后缀匹配的位置，//如果一直找不到那么k值将会变成成0 。就是说主串要从模式开头进行匹配 。}}}

有了计算next数组的算法，那么KMP的实现就很简单了