CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章快速模式匹配算法(KMP)的深入理解由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

恐怕现在用过电脑的人，一定都知道大部分带文本编辑功能的软件都有一个快捷键ctrl+f 吧（比如word）。这个功能主要来完成“查找”，“替换”和“全部替换”功能的，其实这就是典型的模式匹配的应用，即在文本文件中查找串。 1.模式匹配 模式匹配的模型大概是这样的：给定两个字符串变量S和P，其中S成为目标串，其中包含n个字符，P称为模式串，包含m个字符，其中m<=n。从S的给定位置（通常是S的第一个位置）开始搜索模式P。如果找到，则返回模式P在目标串中的位置（即：P的第一个字符在S中的下标）。如果在目标串S中没有找到模式串P，则返回-1.这就是模式匹配的定义啦，下面来看看怎么实现模式匹配算法吧。 2.朴素的模式匹配 朴素的模式匹配算法非常简单，容易理解，大概思路是这样的：从S的第一个字符S0开始，将P中的字符依次和S中字符比较，若S0=P0 && …… && Sm-1 = Pm-1，则证明匹配成功，剩下的匹配无需进行了，返回下标0。若在某一步Si != Pi 则P中剩下的字符也不用比较了，不可能匹配成功了，然后从S中第二个字符开始与P中第一个字符进行比较，同理，也是知道Sm = Pm-1或者找到某个i使得Si != S-1为止。依次类推若知道以S中第n-m个开始字符为止，还没有匹配成功则证明S中不存模式P。（想想为什么这里强调是n-m）这个代码实现应该是非常简单的，具体开始参考strstr函数的内部实现。可以看看百度百科，给个链接http://baike.baidu.com/view/745156.htm，这里不写出来了，还得赶紧进入正题KMP呢。 3.快速模式匹配算法（KMP） 朴素的模式匹配效率不高的主要原因是进行了重复的字符比较。下一次比较和上一次比较没有任何的联系，是朴素模式匹配的缺点，其实上一次比较的比较结果是可以利用的，这就产生了快速模式匹配。在朴素的模式匹配中，目标串S的下标移动是一步一步的，这其实并不好，移动步数没有必要为1。 现在不妨假设，当前匹配情况是这样的：S0 …… St St+1 …… St+j  与 P0 P1…… Pj ，现在正在尝试匹配的字符是St+j+1和Pj+1，并且St+j+1 != Pj+1，言外之意就是说St St+1……St+j和P0 P1……Pj是完全匹配的。那么这个时候，S中下一次匹配开始位置应该是什么呢？？按照朴素的模式匹配，下次比较应该从St+1开始，并且令St+1和P0比较，但是在快速模式匹配中并不是这样，快速模式匹配选择St+j+1和Pk+1比较，K是什么呢？K是这样的一个值，使得P0 P1……Pk 和 Pj-k Pj-k+1……Pj完全匹配，不妨设k=next[j]，因此P0 P1……Pk和St+j-k St+j-k+1 ……St+j完全匹配。那么下一次要进行匹配的两个字符应为St+j+1和Pk+1。S和P都没有回溯到下标0在进行比较，这就是KMP之所以快的原因啦。 现在关键问题来了，这个K怎么能得到呢？如果得到这个K值复杂度高，那这个思路就不好了，其实这个K呢，只和模式串P有关系，并且要求m个k，k = next[j]，因此只要算一次存储到next数组中就可以了，并且时间复杂度和m有关系（线性关系）。看看具体怎么求next数组的值，即求k。 用归纳法求next[]：设next(0) = -1，若已知next(j) = k，欲求得next[j+1]。 （1）如果Pk+1 = Pj+1，显然next[j+1] = k+1.如果Pk+1 != Pj+1，则next[j+1] < next[j]，于是寻找h < k 使得P0 P1……Ph = Pj-h Pj-h+1……Pj = Pk-h Pk-h+1……Pk。也就是说h = next(k);看出来了吧，这是个迭代的过程。（也就是以前的结果对求以后的值有用） （2）如果不存这样的h，说明P0 P1……Pj+1中没有前后相等的子串，因此next[j+1] =-1. （3）如果存在这样的h，继续检验Ph和Pj是否相等。知道找到这中相等的情况，或者确定为-1求next[j+1]的过程结束。 看看实现的代码:

复制代码 代码如下

View Code int next[20] ={0}; //注意返回结果是一个数组next，保存m个k值得地方，即若next[j]=k //则str[0]str[1]…str[k] = str[j-k]str[j-k+1]…str[j] //这样当des[t+j+1]和pat[j+1]匹配失败时，下一个匹配位置为des[t+j+1]和next[j]+1 void Next(char str[],int len) {     next[0] = -1;     for(int j = 1 ; j < len ; j++)     {         int i = next[j-1];         while(str[j] != str[i+1] && i >= 0)//迭代的过程         {             i = next[i];         }         if(str[j] == str[i+1])         {             next[j] = i+1;         }         else         {             next[j] = -1;         }     } } 。

现在有了next数组保存的k值，就可以实现KMP算法了:

复制代码 代码如下

View Code //des是目标串，pat是模式串，len1和len2是串的长度 int kmp(char des[],int len1,char pat[],int len2) {     Next(str2,len2);     int p=0,s=0;     while(p < len2  && s < len1)     {         if(pat[p] == des[s])         {             p++;s++;         }         else         {             if(p==0)             {                 s++;//若第一个字符就匹配失败，则从des的下一个字符开始             }             else             {                 p = next[p-1]+1;//用失败函数确定pat应回溯到的字符             }         }     }     if(p < len2)//整个过程匹配失败     {         return -1;     }     return s-len2; } 。

时间复杂度： 对于Next函数近似接近O（m），KMP算法的时间复杂度为O(n)，所以整个算法的时间复杂度为O(n+m) 空间复杂度： 多引入了O（m）的空间复杂度。 4.应用KMP的一道面试题 给定两个字符串是s1和s2，要判定s2是否能够被s1做循环移位得到的字符串包含。例如s1=AABCD，s2 =CDAA，返回true，因为s1循环移位可以变成CDAAB。给定s1=ACBD和s2=ACBD则返回false。 分析：不难发现对s2移位得到的字符串都将是字符串s1s1的子串，如果s2可以有s1循环移位得到，那么s2一定是s1s1的子串，这时KMP算法是不是就很管用了呢.

最后此篇关于快速模式匹配算法(KMP)的深入理解的文章就讲到这里了,如果你想了解更多关于快速模式匹配算法(KMP)的深入理解的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。