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

相关文章

Python基础文件操作方法超详细讲解(详解版)

《Python基础文件操作方法超详细讲解(详解版)》文件就是操作系统为用户或应用程序提供的一个读写硬盘的虚拟单位,文件的核心操作就是读和写,:本文主要介绍Python基础文件操作方法超详细讲解的相... 目录一、文件操作1. 文件打开与关闭1.1 打开文件1.2 关闭文件2. 访问模式及说明二、文件读写1.

Ubuntu中远程连接Mysql数据库的详细图文教程

《Ubuntu中远程连接Mysql数据库的详细图文教程》Ubuntu是一个以桌面应用为主的Linux发行版操作系统,这篇文章主要为大家详细介绍了Ubuntu中远程连接Mysql数据库的详细图文教程,有... 目录1、版本2、检查有没有mysql2.1 查询是否安装了Mysql包2.2 查看Mysql版本2.

Oracle数据库常见字段类型大全以及超详细解析

《Oracle数据库常见字段类型大全以及超详细解析》在Oracle数据库中查询特定表的字段个数通常需要使用SQL语句来完成,:本文主要介绍Oracle数据库常见字段类型大全以及超详细解析,文中通过... 目录前言一、字符类型(Character)1、CHAR:定长字符数据类型2、VARCHAR2:变长字符数

Win11安装PostgreSQL数据库的两种方式详细步骤

《Win11安装PostgreSQL数据库的两种方式详细步骤》PostgreSQL是备受业界青睐的关系型数据库,尤其是在地理空间和移动领域,:本文主要介绍Win11安装PostgreSQL数据库的... 目录一、exe文件安装 (推荐)下载安装包1. 选择操作系统2. 跳转到EDB(PostgreSQL 的

Python3.6连接MySQL的详细步骤

《Python3.6连接MySQL的详细步骤》在现代Web开发和数据处理中,Python与数据库的交互是必不可少的一部分,MySQL作为最流行的开源关系型数据库管理系统之一,与Python的结合可以实... 目录环境准备安装python 3.6安装mysql安装pymysql库连接到MySQL建立连接执行S

将Mybatis升级为Mybatis-Plus的详细过程

《将Mybatis升级为Mybatis-Plus的详细过程》本文详细介绍了在若依管理系统(v3.8.8)中将MyBatis升级为MyBatis-Plus的过程,旨在提升开发效率,通过本文,开发者可实现... 目录说明流程增加依赖修改配置文件注释掉MyBATisConfig里面的Bean代码生成使用IDEA生

Linux系统配置NAT网络模式的详细步骤(附图文)

《Linux系统配置NAT网络模式的详细步骤(附图文)》本文详细指导如何在VMware环境下配置NAT网络模式,包括设置主机和虚拟机的IP地址、网关,以及针对Linux和Windows系统的具体步骤,... 目录一、配置NAT网络模式二、设置虚拟机交换机网关2.1 打开虚拟机2.2 管理员授权2.3 设置子

Linux系统中卸载与安装JDK的详细教程

《Linux系统中卸载与安装JDK的详细教程》本文详细介绍了如何在Linux系统中通过Xshell和Xftp工具连接与传输文件,然后进行JDK的安装与卸载,安装步骤包括连接Linux、传输JDK安装包... 目录1、卸载1.1 linux删除自带的JDK1.2 Linux上卸载自己安装的JDK2、安装2.1

Java使用Curator进行ZooKeeper操作的详细教程

《Java使用Curator进行ZooKeeper操作的详细教程》ApacheCurator是一个基于ZooKeeper的Java客户端库,它极大地简化了使用ZooKeeper的开发工作,在分布式系统... 目录1、简述2、核心功能2.1 CuratorFramework2.2 Recipes3、示例实践3

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

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