一篇短小精悍的文章让你彻底明白KMP算法中next数组的原理

2023-10-10 04:04

本文主要是介绍一篇短小精悍的文章让你彻底明白KMP算法中next数组的原理,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

以后保持每日一更,由于兴趣较多,更新内容不限于数据结构,计算机组成原理,数论,拓扑学......,所谓:深度围绕职业发展,广度围绕兴趣爱好。往下看今日内容

一.什么是KMP算法

  KMP(Knuth-Morris-Pratt)算法是一种字符串匹配算法,用于在一个较长的文本串中查找一个模式串的出现位置。

二.KMP算法的应用

  这个算法在很多应用中都有重要的作用:

  1. 字符串搜索:KMP算法可以快速在一个长文本中查找一个关键词或者子串的出现位置。因为KMP算法在匹配失败时利用了先前已经匹配过的信息,避免了不必要的回溯,提高了搜索效率。

  2. 文件比较:比如两个文本文件的比较,KMP算法可以用于找到两个文件中相同的部分或者相似的部分,从而进行比较或者合并。

  3. DNA序列匹配:在生物信息学中,KMP算法可以应用于DNA序列比对和DNA片段的查找,这对于基因研究和遗传工程非常重要。

  4. 编辑器中的查找和替换:很多文本编辑器在实现查找和替换功能时会使用KMP算法,用于快速定位和匹配模式串。

三.KMP算法next数组原理(非常重要)

在字符串匹配的KMP算法中,求模式串的next数组值的定义如下:

问:

1)当 j=1时,为什么要取next[1]=0 ?

2)为什么要取max{k},k的最大值为多少?

3)其他情况是什么情况,为什么next取next[j]=1?

解:

1)当模式串中的第一个字符与主串中的第一个字符不匹配时,next[1]=0,表示模式串应该右移一位,主串当前指针往后移动一位,再和模式串的第一个字符进行比较。

2)当主串的第i个字符与模式串的第j个字符不匹配时,主串i不回溯,也就是不向前移动,则假定模式串的第k个字符与主串的第i个字符比较,k值应满足条件1<k<j,并且’p1 p2 ......p(k-1)'='p(j-k+1)p(j-k+2)......p(j-1),即k为模式串的下次比较的位置。k的取值可能有多个,为了不使右移丢失可能的匹配,右移的距离应该取最小,由于j-k表示右移的距离,所以取max{k}。k的最大值为j-1。

3)除了上面两种情况外,发生不匹配时,主串指针i不回溯,在最坏的情况下,模式串从第1个字符开始与主串的第i个字符比较。

四.总结

KMP算法与朴素匹配最明显的一个特点就是,KMP算法很绝,它觉得,过去的事情就让它过去,不必回头,简称“一往无前”。然而,朴素匹配算法很委婉,很想回头挽留,可是最终受伤的总是自己,简称“不堪回首”。

可见,KMP算法是一个高效率,代码简洁,逻辑性巧妙的算法。

这篇关于一篇短小精悍的文章让你彻底明白KMP算法中next数组的原理的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Java Spring 中 @PostConstruct 注解使用原理及常见场景

《JavaSpring中@PostConstruct注解使用原理及常见场景》在JavaSpring中,@PostConstruct注解是一个非常实用的功能,它允许开发者在Spring容器完全初... 目录一、@PostConstruct 注解概述二、@PostConstruct 注解的基本使用2.1 基本代

Golang HashMap实现原理解析

《GolangHashMap实现原理解析》HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持高效的插入、查找和删除操作,:本文主要介绍GolangH... 目录HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

Spring Boot循环依赖原理、解决方案与最佳实践(全解析)

《SpringBoot循环依赖原理、解决方案与最佳实践(全解析)》循环依赖指两个或多个Bean相互直接或间接引用,形成闭环依赖关系,:本文主要介绍SpringBoot循环依赖原理、解决方案与最... 目录一、循环依赖的本质与危害1.1 什么是循环依赖?1.2 核心危害二、Spring的三级缓存机制2.1 三

C#中async await异步关键字用法和异步的底层原理全解析

《C#中asyncawait异步关键字用法和异步的底层原理全解析》:本文主要介绍C#中asyncawait异步关键字用法和异步的底层原理全解析,本文给大家介绍的非常详细,对大家的学习或工作具有一... 目录C#异步编程一、异步编程基础二、异步方法的工作原理三、代码示例四、编译后的底层实现五、总结C#异步编程

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

如何将Python彻底卸载的三种方法

《如何将Python彻底卸载的三种方法》通常我们在一些软件的使用上有碰壁,第一反应就是卸载重装,所以有小伙伴就问我Python怎么卸载才能彻底卸载干净,今天这篇文章,小编就来教大家如何彻底卸载Pyth... 目录软件卸载①方法:②方法:③方法:清理相关文件夹软件卸载①方法:首先,在安装python时,下

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

openCV中KNN算法的实现

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

Go 语言中的select语句详解及工作原理

《Go语言中的select语句详解及工作原理》在Go语言中,select语句是用于处理多个通道(channel)操作的一种控制结构,它类似于switch语句,本文给大家介绍Go语言中的select语... 目录Go 语言中的 select 是做什么的基本功能语法工作原理示例示例 1:监听多个通道示例 2:带