KMP(Knuth-Morris-Pratt)算法

本文主要是介绍KMP(Knuth-Morris-Pratt)算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、朴素匹配算法

也就是暴力匹配算法。设匹配字符串的长度为n，模式串的长度为m，在最坏情况下，朴字符串匹配算法运行时间为O((n - m + 1)m)。如果m = n / 2， 那么该算法的复杂度就是Θ(n ^ 2)。由于不需要预处理，朴素字符串匹配算法运行时间即为其匹配时间。

strstr()函数就可以用这个方法实现，尽管效率不高：

//strstr函数
char *strStr(const char *str, const char *substr) {if (substr == NULL || str == NULL)return NULL;if (!*substr)return const_cast<char*>(str);const char *p1 = str;const char *p2 = substr;const char *p1_advance = str;//p1_advance指针前进strlen(substr)-1位//因为当str中还未匹配的位数小于substr的长度时，肯定不可能再匹配成功了for (p2 = substr + 1; *p2; ++p2)++p1_advance;for (p1 = str; *p1_advance; p1_advance++) {char *p1_old = (char *)p1;p2 = substr;while (*p1 && *p2 && *p1 == *p2) {++p1;++p2;}if (!*p2)return p1_old;p1 = p1_old + 1;}return NULL;
}int main() {char str[100] = {'\0'};char substr[100] = {'\0'};scanf("%s %s", str, substr);if (strStr(str, substr) != NULL)printf("true\n");elseprintf("false\n");
}</span>

二、KMP算法

参考文章：http://www.ruanyifeng.com/blog/2013/05/Knuth–Morris–Pratt_algorithm.html

July的文章把该算法讲得挺透彻了：KMP算法。

       设匹配字符串的长度为n，模式串的长度为m。该算法的匹配时间为Θ(n)，用到了一个辅助函数GetNext()，它在Θ(m)时间内根据模式预先计算出来，并且存储在数组next[0...m]中。模式的前缀函数GetNext包含模式与其自身的偏移进行匹配的信息。这些信息可用于在朴素的字符串匹配算法中避免对无用的偏移进行检测。KMP利用模式串中已知的匹配信息，不再把搜索位置移动到比较过的位置（即不做无用的匹配），这样提高了效率。

KMP完整代码如下：

void GetNext(char* pattern,int next[]) {  int k = -1;  int j = 0;  int length_pattern = strlen(pattern);  next[0] = -1;  while (j < length_pattern - 1) {  //p[k]表示前缀，p[j]表示后缀  if (k == -1 || pattern[j] == pattern[k]) {  ++k;  ++j;  next[j] = k;  }  elsek = next[k];}  
}int KmpSearch(char* text, char* pattern) {  int i = 0;  int j = 0;  int length_text = strlen(text);  int length_pattern = strlen(pattern);int *next = new int[length_pattern];GetNext(pattern, next);for (int i = 0; i < length_pattern; ++i) cout << next[i] << " ";cout << endl;while (i < length_text && j < length_pattern) {  //①如果j = -1,或者当前字符匹配成功(即text[i] == pattern[j]),令i++，j++      if (j == -1 || text[i] == pattern[j]) {  ++i;++j;}else//②如果j != -1,且当前字符匹配失败(即text[i] != pattern[j]),//则令i不变,j = next[j]，next[j]即为j所对应的next值        j = next[j]; }  delete[] next;if (j == length_pattern)  return i - j;  else  return -1;  
}  //int main() {
//	char str[100] = {'\0'};
//	char substr[100] = {'\0'};
//	scanf("%s %s", str, substr);
//	for (int i = 0 ; i < 10; ++i)
//		cout << substr[i] << " ";
//	cout << endl;
//	cout << KmpSearch(str, substr) << endl;
//}

由于需要根据自己的理解对文章内容进行标注，所以将july的文章摘录如下：

-----------------------以下为july文章--------------------------------

从头到尾彻底理解KMP

作者：July
时间：最初写于2011年12月，2014年7月21日晚10点 全部删除重写成此文，随后的半个多月不断反复改进。

1. 引言

    本KMP原文最初写于2年多前的2011年12月，因当时初次接触KMP，思路混乱导致写也写得混乱。所以一直想找机会重新写下KMP，但苦于一直以来对KMP的理解始终不够，故才迟迟没有修改本文。

    然近期因在北京开了个算法班，专门讲解数据结构、面试、算法，才再次仔细回顾了这个KMP，在综合了一些网友的理解、以及跟我一起讲算法的两位讲师朋友曹博、邹博的理解之后，写了9张PPT，发在微博上。随后，一不做二不休，索性将PPT上的内容整理到了本文之中（后来文章越写越完整，所含内容早已不再是九张PPT 那样简单了）。

    KMP本身不复杂，但网上绝大部分的文章（包括本文的2011年版本）把它讲混乱了。下面，咱们从暴力匹配算法讲起，随后阐述KMP的流程 步骤、next 数组的简单求解 递推原理 代码求解，接着基于next 数组匹配，谈到有限状态自动机，next 数组的优化，KMP的时间复杂度分析，最后简要介绍两个KMP的扩展算法。

    全文力图给你一个最为完整最为清晰的KMP，希望更多的人不再被KMP折磨或纠缠，不再被一些混乱的文章所混乱，有何疑问，欢迎随时留言评论，thanks。

2. 暴力匹配算法

    假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？

    如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：

• 如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；
• 如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。

    举个例子，如果给定文本串S“BBC ABCDAB ABCDABCDABDE”，和模式串P“ABCDABD”，现在要拿模式串P去跟文本串S匹配，整个过程如下所示：

    1. S[0]为B，P[0]为A，不匹配，执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S[1]跟P[0]匹配，相当于模式串要往右移动一位（i=1，j=0）

    2. S[1]跟P[0]还是不匹配，继续执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S[2]跟P[0]匹配（i=2，j=0），从而模式串不断的向右移动一位（不断的执行“令i = i - (j - 1)，j = 0”，i从2变到4，j一直为0）

    3. 直到S[4]跟P[0]匹配成功（i=4，j=0），此时按照上面的暴力匹配算法的思路，转而执行第①条指令：“如果当前字符匹配成功（即S[i] == P[j]），则i++，j++”，可得S[i]为S[5]，P[j]为P[1]，即接下来S[5]跟P[1]匹配（i=5，j=1）

     

    4. S[5]跟P[1]匹配成功，继续执行第①条指令：“如果当前字符匹配成功（即S[i] == P[j]），则i++，j++”，得到S[6]跟P[2]匹配（i=6，j=2），如此进行下去

    

    5. 直到S[10]为空格字符，P[6]为字符D（i=10，j=6），因为不匹配，重新执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，相当于S[5]跟P[0]匹配（i=5，j=0）

     

    6. 至此，我们可以看到，如果按照暴力匹配算法的思路，尽管之前文本串和模式串已经分别匹配到了S[9]、P[5]，但因为S[10]跟P[6]不匹配，所以文本串回溯到S[5]，模式串回溯到P[0]，从而让S[5]跟P[0]匹配。

    而S[5]肯定跟P[0]失配。为什么呢？因为在之前第4步匹配中，我们已经得知S[5] = P[1] = B，而P[0] = A，即P[1] != P[0]，故S[5]必定不等于P[0]，所以回溯过去必然会导致失配。那有没有一种算法，让i 不往回退，只需要移动j 即可呢？

    答案是肯定的。这种算法就是本文的主旨KMP算法，它利用之前已经部分匹配这个有效信息，保持i 不回溯，通过修改j 的位置，让模式串尽量地移动到有效的位置。

3. KMP算法

3.1 定义

这篇关于KMP(Knuth-Morris-Pratt)算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---