KMP(Knuth-Morris-Pratt)算法

2024-08-28 04:08
文章标签 算法 kmp morris knuth 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。
    理清楚了暴力匹配算法的流程及内在的逻辑，咱们可以写出暴力匹配的代码，如下：
  1. int ViolentMatch(char* s, char* p)  
  2. {  
  3.     int sLen = strlen(s);  
  4.     int pLen = strlen(p);  
  5.   
  6.     int i = 0;  
  7.     int j = 0;  
  8.     while (i < sLen && j < pLen)  
  9.     {  
  10.         if (s[i] == p[j])  
  11.         {  
  12.             //①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++      
  13.             i++;  
  14.             j++;  
  15.         }  
  16.         else  
  17.         {  
  18.             //②如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0      
  19.             i = i - j + 1;  
  20.             j = 0;  
  21.         }  
  22.     }  
  23.     //匹配成功，返回模式串p在文本串s中的位置，否则返回-1  
  24.     if (j == pLen)  
  25.         return i - j;  
  26.     else  
  27.         return -1;  
  28. }  

    举个例子，如果给定文本串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 定义

    Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP算法”，常用于在一个文本串S内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表，故取这3人的姓氏命名此算法。
    下面先直接给出KMP的算法流程（ 如果感到一点点不适，没关系，坚持下，稍后会有具体步骤及解释，越往后看越会柳暗花明☺）：
  • 假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置
    • 如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；
    • 如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移动了j - next [j] 位。
      • 换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值（next 数组的求解会在下文的3.3.3节中详细阐述），即移动的实际位数为：j - next[j]，且此值大于等于1。
    很快，你也会意识到 next 数组各值的含义：代表当前字符之前的字符串中，有多大长度的相同前缀后缀。例如如果next [j] = k，代表j 之前的字符串中有最大长度为k 的相同前缀后缀。
    此也意味着在某个字符失配时，该字符对应的next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next [j] 的位置）。如果next [j] 等于0或-1，则跳到模式串的开头字符，若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某个字符，而不是跳到开头，且具体跳过了k 个字符。
    转换成代码表示࿰

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


http://www.chinasem.cn/article/1113688。

相关文章

openCV中KNN算法的实现

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库，它提供了各
阅读更多...
springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...
SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...
Java时间轮调度算法的代码实现

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组（时间轮）和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时
阅读更多...
如何通过Golang的container/list实现LRU缓存算法

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣：146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.
阅读更多...
golang字符串匹配算法解读

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt（KMP）算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串（称为
阅读更多...
通俗易懂的Java常见限流算法具体实现

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》：本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1
阅读更多...
Python中的随机森林算法与实战

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例：使用随机森林预测鸢尾花品种4.1
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2