KMP(Knuth-Morris-Pratt)算法,详细版

2024-03-22 11:10

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

KMP(Knuth-Morris-Pratt)算法

1、KMP算法

在目标串T中搜索模式串P

​ 由于强制算法(暴力搜素算法)在找到不匹配的字符时,只能把模式串P(相对于目标串T)移动一个位置,导致大量的操作重复,冗余的次数随目标串,或模式串长度的增长,使得代码的执行效率直线下降。

​ 为了使搜素的效率提高,且不遗漏每一处匹配,KMP算法通过利用匹配失败处的位置信息,进行改进,使失败的匹配结果也能得到利用,加快字符串匹配效率

2、过程

2.1、给定目标串T,和模式串P

注意:一个字符串的前缀可以包括其本身

   0 1 2 3 4 5 6 7 8 9 10 11
T: a b c a b d a b a b c d
P: a b a b c

2.2、对模式串P创建前缀表PrefixTable

  模式串P前缀    最长公共前后缀       最长公共前后缀长度  index       prefix[index]
----------------------------------------------------------------------------------------
-1|          |      -          |        -        |  0	 |       -1      |
0 |	a        |     null        |        0        | 	1	 |        0      |
0 |	a b      |     null        |        0        |  2	 |        0      |
1 |	a b a    |      a          |        1        |  3	 |        1      |
2 |	a b a b  |      ab         |        2        |  4	 |        2      |
- |	a b a b c|     null        |        0        |  -	 |         -     |这一行不要

2.2.1具体操作:

  1. 写出模式串的前缀(由于包含本身)
  2. 根据模式串的前缀,写出对应的最长公共前后缀长度[0 0 1 2 0]
  3. [0 0 1 2 0],去掉最后一个元素,整体向右移动,在最前面写**-1**-------->[-1 0 0 1 2 ]

2.2.2得到前缀表

P: a  b  a  b  c-1  0  0  1  2  <---a下面应该是0,为了代码写起来方便写成-1

2.3 KMP进行过程

2.3.1、

外链图片转存失败(img-0hJ5lPEz-1567419238965)(![C:\Users\张腾森\Desktop\算法\j1.png)]

​ 1.当模式串P和目标串T匹配到第4个字符时,T[3] != p[3],这时注意到P串下面的与P串相对应的前缀表内容,取出prefix[3] == 1,然后把P串的p[ prefix[3] == 1 ]去和T[3]做比较。

​ 总结1-1:当模式串P[j]和目标串T[i]不匹配时**(i任意取的,完全是模式串在目标串上移动的,所以p串可能匹配t串的任意位置)**,获取P串对应的下标j,在用相同的下标j去获取前缀表中的内容int k = prefix[j]
然后用p[k]去和T[i]匹配,

[外链图片转存失败(img-Bi6PM7OZ-1567419238968)(C:\Users\张腾森\Desktop\算法\j2.png)]

​ 2.此时会发现,p[1]==b,t[3]==1;p[1]!=t[3],不匹配,于是继续上面的操作,在模式串P中取出不匹配处的下标·j==0,在通过该下标去获取前缀表的内容prefix[j==0]==0,再用p[0]去和t[3]做匹配

[外链图片转存失败(img-gbgHsZS8-1567419238970)(C:\Users\张腾森\Desktop\算法\j3.png)]

​ 3、发现p[0]==T[3],这时,移动目标串T的位置t[3---->4]p[0---->1],于是用T[4]==c,与p[0]==b进行匹配,发现T[4]!=p[1],重复第二步,获取模式串P在不匹配处的下标j==1,在通过该下标j==1找到前缀表中对应的值prefix[j==1]==0,于是用模式串j==0节点P[j==0]去对应t[4],

​ 总结1-2:当模式串P和目标串T同时匹配上时,目标串T和模式串P移动到下一个节点(i++,j++)进行匹配,如果不匹配,则重复总结1-1

4.注意到,p[1]==b;t[4]==c;是不匹配的,于是去前缀表prefix[1]==0;于是用p[0]==a去和t[4]==c去匹配,结果还是不匹配,**此时在去前缀
表取值发现prefix[0]== -1,这时候要做的就是用P[-1]==?去和t[4]==c做匹配,换就话说,就是把整个p串右移一个位置,和t的下一个元
素进行匹配(i++,j++)**

[外链图片转存失败(img-1kZPeIfU-1567419238973)(C:\Users\张腾森\Desktop\算法\j5.png)]

​ 5,继续匹配后,发现已经找到了第一个匹配成功的位置,此时返回在目标串中的当前索引位置i-模式串的长度

即第一个匹配成功的位置,

[外链图片转存失败(img-4mhtA7nn-1567419238974)(C:\Users\张腾森\Desktop\算法\j8.png)]

​ 6.当匹配成功时p的当前索引是4,于是取前缀表prefix[4]==2,再用p[2]==a,去和T串匹配,结果发现,到最和一个元素了(有可能出界),匹配结束。

[外链图片转存失败(img-qrPPNass-1567419238974)(C:\Users\张腾森\Desktop\算法\j9.png)]

3、代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void prefix_table(char pattern[], int prefix[], int n) {prefix[0] = 0;int len = 0;int	i =1;	while(i<n){if ( pattern[i] == pattern[len] ) {len++ ;prefix[i] = len;i++ ;}else {if(len > 0){len = prefix[ len-1];}else {prefix[i] = len;i++ ;}}}
}
void move_prefix_table(int prefix[], int n) {int i;for(i=n-1;i>0;i--){prefix[i] = prefix[i-1];}prefix[0] = -1;
}
void kmp_search( char text[], char pattern[]) {int n = strlen( pattern);//<----string.hint m = strlen( text );int* prefix =(int*)malloc( n*sizeof(int));//<--stdlib.h//int prefix[n]; prefix_table(pattern, prefix, n);move_prefix_table(prefix, n);
// text[i], Len( text)=m
// pattern[j] ,Len(pattern) = nint i=0;int j=0; while(i<m){if (j==n-1&&text[i]==pattern[j]) {printf("Found pattern at %d\n", i - j);j=prefix[j]; }if (text[i] == pattern[j]) {i++; j++;}else {j= prefix[j];if (j == -1) {i++; j++ ;}}}
} int main() {char pattern[] = "ABABCABAA";char text[]= "ABABABCABAABABABAB";kmp_search(text,pattern);return 0;
}

4、结果

[外链图片转存失败(img-shaFlpm4-1567419238980)(C:\Users\张腾森\Desktop\算法\j10.png)]

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



http://www.chinasem.cn/article/835182

相关文章

使用Docker构建Python Flask程序的详细教程

《使用Docker构建PythonFlask程序的详细教程》在当今的软件开发领域,容器化技术正变得越来越流行,而Docker无疑是其中的佼佼者,本文我们就来聊聊如何使用Docker构建一个简单的Py... 目录引言一、准备工作二、创建 Flask 应用程序三、创建 dockerfile四、构建 Docker

Python设置Cookie永不超时的详细指南

《Python设置Cookie永不超时的详细指南》Cookie是一种存储在用户浏览器中的小型数据片段,用于记录用户的登录状态、偏好设置等信息,下面小编就来和大家详细讲讲Python如何设置Cookie... 目录一、Cookie的作用与重要性二、Cookie过期的原因三、实现Cookie永不超时的方法(一)

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

SpringBoot整合liteflow的详细过程

《SpringBoot整合liteflow的详细过程》:本文主要介绍SpringBoot整合liteflow的详细过程,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋...  liteflow 是什么? 能做什么?总之一句话:能帮你规范写代码逻辑 ,编排并解耦业务逻辑,代码

浏览器插件cursor实现自动注册、续杯的详细过程

《浏览器插件cursor实现自动注册、续杯的详细过程》Cursor简易注册助手脚本通过自动化邮箱填写和验证码获取流程,大大简化了Cursor的注册过程,它不仅提高了注册效率,还通过友好的用户界面和详细... 目录前言功能概述使用方法安装脚本使用流程邮箱输入页面验证码页面实战演示技术实现核心功能实现1. 随机

HTML img标签和超链接标签详细介绍

《HTMLimg标签和超链接标签详细介绍》:本文主要介绍了HTML中img标签的使用,包括src属性(指定图片路径)、相对/绝对路径区别、alt替代文本、title提示、宽高控制及边框设置等,详细内容请阅读本文,希望能对你有所帮助... 目录img 标签src 属性alt 属性title 属性width/h

CSS3打造的现代交互式登录界面详细实现过程

《CSS3打造的现代交互式登录界面详细实现过程》本文介绍CSS3和jQuery在登录界面设计中的应用,涵盖动画、选择器、自定义字体及盒模型技术,提升界面美观与交互性,同时优化性能和可访问性,感兴趣的朋... 目录1. css3用户登录界面设计概述1.1 用户界面设计的重要性1.2 CSS3的新特性与优势1.

CSS中的Static、Relative、Absolute、Fixed、Sticky的应用与详细对比

《CSS中的Static、Relative、Absolute、Fixed、Sticky的应用与详细对比》CSS中的position属性用于控制元素的定位方式,不同的定位方式会影响元素在页面中的布... css 中的 position 属性用于控制元素的定位方式,不同的定位方式会影响元素在页面中的布局和层叠关

在Windows上使用qemu安装ubuntu24.04服务器的详细指南

《在Windows上使用qemu安装ubuntu24.04服务器的详细指南》本文介绍了在Windows上使用QEMU安装Ubuntu24.04的全流程:安装QEMU、准备ISO镜像、创建虚拟磁盘、配置... 目录1. 安装QEMU环境2. 准备Ubuntu 24.04镜像3. 启动QEMU安装Ubuntu4

SpringBoot整合Flowable实现工作流的详细流程

《SpringBoot整合Flowable实现工作流的详细流程》Flowable是一个使用Java编写的轻量级业务流程引擎,Flowable流程引擎可用于部署BPMN2.0流程定义,创建这些流程定义的... 目录1、流程引擎介绍2、创建项目3、画流程图4、开发接口4.1 Java 类梳理4.2 查看流程图4