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

相关文章

IntelliJ IDEA 中配置 Spring MVC 环境的详细步骤及问题解决

《IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决》:本文主要介绍IntelliJIDEA中配置SpringMVC环境的详细步骤及问题解决,本文分步骤结合实例给大... 目录步骤 1:创建 Maven Web 项目步骤 2:添加 Spring MVC 依赖1、保存后执行2、将新的依赖

如何为Yarn配置国内源的详细教程

《如何为Yarn配置国内源的详细教程》在使用Yarn进行项目开发时,由于网络原因,直接使用官方源可能会导致下载速度慢或连接失败,配置国内源可以显著提高包的下载速度和稳定性,本文将详细介绍如何为Yarn... 目录一、查询当前使用的镜像源二、设置国内源1. 设置为淘宝镜像源2. 设置为其他国内源三、还原为官方

最详细安装 PostgreSQL方法及常见问题解决

《最详细安装PostgreSQL方法及常见问题解决》:本文主要介绍最详细安装PostgreSQL方法及常见问题解决,介绍了在Windows系统上安装PostgreSQL及Linux系统上安装Po... 目录一、在 Windows 系统上安装 PostgreSQL1. 下载 PostgreSQL 安装包2.

MySql match against工具详细用法

《MySqlmatchagainst工具详细用法》在MySQL中,MATCH……AGAINST是全文索引(Full-Textindex)的查询语法,它允许你对文本进行高效的全文搜素,支持自然语言搜... 目录一、全文索引的基本概念二、创建全文索引三、自然语言搜索四、布尔搜索五、相关性排序六、全文索引的限制七

python中各种常见文件的读写操作与类型转换详细指南

《python中各种常见文件的读写操作与类型转换详细指南》这篇文章主要为大家详细介绍了python中各种常见文件(txt,xls,csv,sql,二进制文件)的读写操作与类型转换,感兴趣的小伙伴可以跟... 目录1.文件txt读写标准用法1.1写入文件1.2读取文件2. 二进制文件读取3. 大文件读取3.1

Linux内核参数配置与验证详细指南

《Linux内核参数配置与验证详细指南》在Linux系统运维和性能优化中,内核参数(sysctl)的配置至关重要,本文主要来聊聊如何配置与验证这些Linux内核参数,希望对大家有一定的帮助... 目录1. 引言2. 内核参数的作用3. 如何设置内核参数3.1 临时设置(重启失效)3.2 永久设置(重启仍生效

如何在Mac上安装并配置JDK环境变量详细步骤

《如何在Mac上安装并配置JDK环境变量详细步骤》:本文主要介绍如何在Mac上安装并配置JDK环境变量详细步骤,包括下载JDK、安装JDK、配置环境变量、验证JDK配置以及可选地设置PowerSh... 目录步骤 1:下载JDK步骤 2:安装JDK步骤 3:配置环境变量1. 编辑~/.zshrc(对于zsh

使用Node.js制作图片上传服务的详细教程

《使用Node.js制作图片上传服务的详细教程》在现代Web应用开发中,图片上传是一项常见且重要的功能,借助Node.js强大的生态系统,我们可以轻松搭建高效的图片上传服务,本文将深入探讨如何使用No... 目录准备工作搭建 Express 服务器配置 multer 进行图片上传处理图片上传请求完整代码示例

openCV中KNN算法的实现

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

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve