字符串匹配KMP算法

  本文摘要：什么是KMPKMP(D.E.Knuth,J.H.Morris,V.R.Prat)是三个发现者的名字首字母命名的。用于字符串匹配的经典算法。 通例匹配算法这个算法很抽象，研究了些时间才逐步弄懂内里的一些秘密之处，并借此记载下来，以便后期回首。

什么是KMPKMP(D.E.Knuth,J.H.Morris,V.R.Prat)是三个发现者的名字首字母命名的。用于字符串匹配的经典算法。

通例匹配算法这个算法很抽象，研究了些时间才逐步弄懂内里的一些秘密之处，并借此记载下来，以便后期回首。通例字符串匹配方式： 主串:ABC ABCDAB ABCDABCDABDE 模式串:ABCDABD 我们要在主串里查找匹配串是否存在，那么通例匹配方式如下：主串和模式串都重新开始匹配，当泛起不匹配的字符时，如图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 前缀和后缀的荟萃为空 共有元素长度为0AB 前缀【A】,后缀【B】 共有元素长度为0ABC 前缀【A,AB】,后缀【BC, C】 共有元素长度为0ABCD 前缀【A,AB,ABC】,后缀【BCD,CD,D】 共有元素长度为0ABCDA 前缀【A,AB,ABC,ABCD】,后缀【BCDA,CDA,DA,A】 共有元素长度为1ABCDAB 前缀【A,AB,ABC,ABCDA】,后缀【BCDAB,CDAB,DAB,AB,B】 共有元素长度为2ABCDABD 前缀【A,AB,ABC,ABCDAB】,后缀【BCDABD,CDABD,DABD,ABD,BD,D】 共有元素长度为0在法式中部门匹配表可以使用一个数组来生存，可以命名为next数组，next数组的下标为当前正在和主串举行比力的字符下标，其值是当前字符的好前缀和洽后缀共有元素的长度。

我们约定next[0]为-1，那么上面的部门匹配转换成next数组如下：next[0]=-1 A A字符的好前缀和洽后缀共有元素长度为0next[1]=0 AB B字符的好前缀和洽后缀共有元素长度为0next[2]=0 ABC C字符的好前缀和洽后缀共有元素长度为0next[3]=0 ABCD D字符的好前缀和洽后缀共有元素长度为0next[4]=1 ABCDA A字符的好前缀和洽后缀共有元素长度为1next[5]=2 ABCDAB B字符的好前缀和洽后缀共有元素长度为2next[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;//第一个元素的共有元素约定为-1 while(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的实现就很简朴了/**s:主串 slen:主串长度 p:模式串 plen:模式串长度 next:已经盘算过的next数组 res:匹配的下标位置**/int kmp(char*s , int slen, char*p, int plen, int *next, int *res){ int s_index, p_index=0, res_index=0; for(s_index = 0; s_index < slen; s_index++){ while(p_index > 0 && s[s_index] != p[p_index]){ //下一个匹配位为next数组的第j-1位 p_index = next[p_index-1]+1; } if(s[s_index] == p[p_index]){ p_index ++;//如果相等就都往后移一位 } //如果匹配串的第一位一直和模式串第一位不相等，那么模式串id s_index一直往后移 if(p_index == plen){ res[res_index++] = s_index-p_index+1;//应为当模式串和匹配串相等时，匹配串的下标会加1，所以会多减1，后面要加上 p_index = 0; } } return res_index;}说明： 以上仅仅代表自己的想法。

本文关键词：博亚体育app官网下载ios,字符串,匹配,KMP,算法,什么,是,KMPKMP,D.E.Knuth

本文来源：博亚体育app官网下载ios-www.njhdbfc.com