-
kmp算法next计算方法_七分钟理解什么是 KMP 算法
2020-11-23 20:04:17本文是介绍 什么是 BF算法、KMP算法、BM算法 三部曲之一。KMP算法 内部涉及到的数学原理与知识太多,本文只会对 KMP算法 的运行过程、 部分匹配表 、next数组 进行介绍,如果理解了这三点再去阅读其它有关 KMP算法 ...本文是介绍 什么是 BF算法、KMP算法、BM算法 三部曲之一。
KMP算法 内部涉及到的数学原理与知识太多,本文只会对 KMP算法 的运行过程、 部分匹配表 、next数组 进行介绍,如果理解了这三点再去阅读其它有关 KMP算法 的文章肯定能有个清晰的认识。
以下的文字描述请结合视频动画来阅读~
https://www.zhihu.com/video/1140625800863752192定义
Knuth-Morris-Pratt 字符串查找算法,简称为 KMP算法,常用于在一个文本串 S 内查找一个模式串 P 的出现位置。
这个算法由 Donald Knuth、Vaughan Pratt、James H. Morris 三人于 1977 年联合发表,故取这 3 人的姓氏命名此算法。
是不是感觉 Donald Knuth 这个名字很眼熟?没错,在前面 这或许是讲解 Knuth 洗牌算法最好的文章 一文中也出现了他!
下面直接给出 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] 位
- 换言之,将模式串 P 失配位置的 next 数组的值对应的模式串 P 的索引位置移动到失配处
看不明白?直接看动画!
运行过程
以下图文本串 S 与模式串 P 为例:
首先,列出模式串 P 的所有子串:
然后,求得每一个子串的所有前缀与后缀。
前缀 指除了最后一个字符以外,一个字符串的全部头部组合;后缀 指除了第一个字符以外,一个字符串的全部尾部组合。
以第五列为例进行演示。
前缀为
后缀为
因此,它的前缀后缀的公共元素的最大长度为 2。
求得原模式串 P 的子串对应的各个前缀后缀的公共元素的 最大长度表 下图。
根据最大长度表 去求 next 数组:next 数组相当于“最大长度值” 整体向右移动一位,然后初始值赋为-1。
好了,获取了 next 数组 后,KMP 算法 的操作就很清晰了。
将模式串 P 与文本串 S 的字母一个个进行匹配,当失配的时候,模式串向右移动。
怎么移动?
比如模式串的 b 与文本串的 c 失配了,找出失配处模式串的 next数组 里面对应的值,这里为 0,然后将索引为 0 的位置移动到失配处。
后记
如果大家看这一章能大概理解 KMP算法 的运行过程的话,那么后续对 KMP算法 的更深入讲解,比如代码实现、next数组优化、时间复杂度分析等知识点肯定也是理解的。
我的专栏:
和程序员小吴一起学算法zhuanlan.zhihu.com -
什么是算法
2020-12-31 23:36:31什么是算法 写这篇文章的原因是发现自己身边一起学习编程的人,自己读得懂程序,但是又写不出代码。自己也是程序的算法是自学的,分享一些自己看书写得比较通俗的文章和自己学习的方法。 一个程序主要包括以下两...写这篇文章的原因是发现自己身边一起学习编程的人,自己读得懂程序,但是又写不出代码。
一个程序主要包括以下两方面的信息:
(1〉对数据的描述。在程序中要指定用到哪些数据以及这些数据的类型和数据的组织形式。这就是数据结构(data structure)。
(2)对操作的描述。即要求计算机进行操作的步骤,也就是算法(algorithm)。
数据是操作的对象,操作的目的是对数据进行加.工处理,以得到期望的结果。打个比方,厨师制作菜肴,需要有菜谱,菜谱上一般应说明:①所用配料,指出为了做出顾客所指定的菜肴,应该使用哪些材料﹔②操作步骤,指出有了这些原料,应按什么样的步骤进行加工,才能做出所需的菜肴。
没有原料是无法加工成所需菜肴的,而对同一些原料可以加工出不同风味的菜肴。作为程序设计人员,必须认真考虑和设计数据结构和操作步骤(即算法)。著名计算机科学家沃思(Nikiklaus Wirth)提出一个公式:
算法+数据结构=程序
…
————摘自谭浩强《C语言程序设计》什么是算法
做任何事情都有一定的步骤。
例如:
你想从北京去天津开会,首先要去买火车票,然后按时乘坐地铁到北京站,登上火车,到天津站后坐汽车到会场,参加会议;
你要买电视机,先要选好货物,然后开票,付款,拿发票,取货,打车回家;
要考大学,首先要填志愿表,交报名费,拿到准考证,按时参加考试,得到录取通知书,到指定学校报到注册等。
这些步骤都是按一定的顺序进行的,缺一不可,次序错了也不行。从事各种工作和活动,都必须事先想好进行的步骤,然后按部就班地进行,才能避免产生错乱。实际上,在日常生活中,由于已养成习惯,所以人们并没意识到每件事都需要事先设计出“行动步骤”。例如吃饭、上学、打球和做作业等,事实上都是按照一定的规律进行的,只是人们不必每次都重复考虑它而已。
不要认为只有“计算”的问题才有算法。广义地说,为解决一个问题而采取的方法和步骤,就称为“算法”。例如,描述太极拳动作的图解,就是“太极拳的算法”。一首歌曲的乐谱,也可以称为该歌曲的算法,因为它指定了演奏该歌曲的每一个步骤,按照它的规定就能演奏出预定的曲子。
————摘自谭浩强《C语言程序设计》总结
上面节选了一篇自己看书对算法概念讲解还是比较通俗的一篇文章,自己也是刚刚入门算法不久,教我们C语言的老师说过,如果各种编程语言与程序语法比作武功的“招式”的话,那么数据结构和算法也就比作“内功”。
-
第2章 算法程序的灵魂 _算法为什么是计算系统的灵魂
2020-03-27 09:20:072.4.5用伪代码表示算法 自学 2.4.6用计算机语言表示算法 自学 2.5结构化程序设计方法 自学 第2章 算法---程序的灵魂 一个程序主要包括以下两方面的信息 (1) 对数据的描述在程序中要指定用到哪些数据以及这些数据的... -
第2章 什么是算法
2020-07-18 14:19:23算法: 对操作的描述。要求计算机进行操作的步骤。 著名计算机科学家沃思提出一个公式:算法 + 数据结构 = 程序 。直到今天,这个公式对于过程化程序来说依然是适用的。 实际上,一个过程化的程序除了以上两个...2.1 程序 = 算法 + 数据结构
一个程序主要包括以下两方面的信息:
- 数据结构: 对数据的描述。在程序中要指定用到哪些数据,以及这些数据的类型和数据的组织形式。
- 算法: 对操作的描述。要求计算机进行操作的步骤。
著名计算机科学家沃思提出一个公式:算法 + 数据结构 = 程序 。直到今天,这个公式对于过程化程序来说依然是适用的。
实际上,一个过程化的程序除了以上两个主要因素之外,还应当采用结构化程序设计方法进行程序设计,并且用某一种计算机语言表示。因此,算法、数据结构、程序设计方法和语言工具 4 个方面是一个程序设计人员所应具备的知识,在设计一个程序时要综合运用这几方面的知识。在这 4 个方面中,算法是灵魂,数据结构是加工对象,语言是工具,编程需要采用合适的方法。
2.2 什么是算法
- 广义地说,为解决一个问题而采取的方法和步骤,就称为 “算法” 。
- 对同一个问题,可以有不同的解题方法和步骤。
- 为了有效地进行解题,不仅需要保证算法正确,还要考虑算法的质量,选择合适的算法。
计算机算法可分为两大类别:
- 数值运算算法: 数值运算的目的是求数值解。由于数值运算往往有现成的模型,可以运用数值分析方法,因此对数值运算的算法的研究比较深入,算法比较成熟。
- 非数值运算算法: 计算机在非数值运算方面的应用远超在数值运算方面的应用。非数值运算的种类繁多,要求各异,需要使用者参考已有的类似算法,重新设计解决特定问题的专门算法。
-
python的算法是指_Python算法的七个重要特征
2021-01-13 06:27:28算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制,也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合...算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制,也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。算法是Python开发中重要知识技能,不可避免的要使用到该技能,那么,Python算法有什么特点呢?
一个Python算法应该具有以下七个重要的特征:
有穷性(Finiteness):算法的有穷性是指算法必须能在执行有限个步骤之后终止;
确切性(Definiteness):算法的每一步骤必须有确切的定义;
输入项(Input):一个算法有0个或多个输入,以刻画运算对象的初始情况,所谓0个输入是指算法本身定出了初始条件;
输出项(Output):一个算法有一个或多个输出,以反映对输入数据加工后的结果。没有输出的算法是毫无意义的;
可行性(Effectiveness):算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步,即每个计算步都可以在有限时间内完成(也称之为有效性);
高效性(High efficiency):执行速度快,占用资源少;
健壮性(Robustness):对数据响应正确。
Python算法除了具有以上特征,还和时间和空间有关系,不同的算法可能用不同的时间、空间或效率来完成同样的任务,因此,一个Python算法的优劣可以用空间复杂度与时间复杂度来衡量。
兔子动态换IP软件可以实现一键IP自动切换,千万IP库存,自动去重,支持电脑、手机多端使用,智能加速技术多IP池自动分配,数据优化智能模拟百万IP访问,兔子动态IP代理作为动态IP行业的领导者,旨在为各行业提供最优质的网络服务。
标签:七个,输出,Python,IP,算法,执行,输入
来源: https://blog.51cto.com/14417194/2475632
-
算法及算法的表示培训课件.pptx
2020-06-15 14:48:573.4 算法及其实现一算法及算法的表示在小品钟点工中宋丹丹讲了这样一个笑话说要把大象装冰箱一共分几步...什么是算法它有什么特点2.算法常用的表示方法有哪些 3. 算法的流程图表示检 测所谓算法就是解题方法的精确描述 -
最小生成树算法【图解】:一文带你理解什么是Prim算法和Kruskal算法
2020-04-14 16:40:00假设以下情景,有一块木板,板上钉上了一些钉子,这些钉子可以由一些细绳连接起来。假设每个钉子可以通过一根或者多根细绳连接起来,那么一定...以上这些问题都可以归纳为最小生成树问题,用正式的表述方法描述为:... -
算法
2020-04-28 14:55:10算法 开发工具与关键技术:Visual Studio / 算法是数据的林间结构 作者:郑名方 撰写时间:2020年4月28日 算法是什么呢?算法是求解问题方法步骤的集合。 算法的概念和特性: ...正确性的含义是算法对于一切合... -
1.2 算法的基本概念和算法评估
2020-09-08 07:54:39本篇内容主要是算法的基本概念和算法评估的方法,话不多说,上正文。 什么是算法? 俗话说得好“程序=数据结构+算法”!那什么是算法呢?算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,是计算机... -
数据结构与算法(Java 描述)-邓俊辉
2018-05-25 15:26:06纳与分类,着重介绍了归并排序算法与快速排序算法,并给出了此类算法的复杂度下界。结合串结 构的应用,第九章着重讨论了串匹配问题,从蛮力算法出发,采用不同的启发式加速策略,分别介 绍了 KMP 算法及 BM 算法。 ... -
关于《数据结构与算法分析 C语言描述》中删除表的一个问题?
2016-10-14 09:57:32以下程序是书中给出的删除表的方法 ``` void DeleteList(List L) { Position P, Tmp; P = L->Next;/*Header assumed*/ L->Next = NULL; while(P != NULL) { Tmp = P->Next; free(P); P = ... -
考研 算法【数据结构】时间复杂度的计算 配套例子详解
2018-09-17 16:38:55一、什么是算法: 算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。 算法的特征: 一个算法应该具有以下五个重要的特征: 有... -
按复杂度有效性递减排序_令你茅塞顿开的Python排序算法
2020-12-06 21:53:56算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算... -
算法基础 2
2019-12-30 15:59:15之后学习算法的方法是用编程语言编写的程序来实现算法,这样做有以下原因; 程序是对算法精确、优雅和完全的描述; 可以通过运行程序来学习算法的各种性质; 可以在应用程序中直接使用这些算法。 静态方法 在... -
【数据结构和算法】算法概述
2021-01-02 18:41:00算法 就是解决问题的方法描述,是指令的有限序列。 一个算法应该具备以下5个重要的特性 1、有穷性: 一个合理的算法对于合理的输入需要在有穷步之后结束,且每一步都需要在有穷时间内完成。 2、确定性 算法中的每... -
算法分析复习参考.pdf
2020-11-29 12:00:501 什么是算法算法有哪些基本特征请指出算法同程序的相同 点与不同点 答算法是解决问题的方法或过程是满足以下四个性质的指令序列 1输入有0个以上的输入 2 输出至少有1个输出 3 确定性指令清晰无歧义 4 有限性指令... -
C语言基础学习-程序的灵魂【算法】
2020-03-05 23:41:28对操作的描述(算法) a.数据是操作的对象,操作的目的是对数据进行加工处理,以得到期望的结果。 著名计算机科学家沃思提出了一个公式: 数据结构 + 算法 = 程序 故一名程序设计人员应具备: 算法(解决“做什么... -
Python算法特点
2018-08-17 16:37:26算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制,也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合... -
算法分析:时间和空间复杂度
2018-08-27 04:06:20算法(Algorithm):是对特定问题求解方法或步骤的一种描述。一个算法可以用多种方法描述,主要有: 使用自然语言描述; 使用形式语言描述; 使用计算机程序设计语言描述。 注:算法和程序是两个不同的概念。一... -
利用朴素贝叶斯算法进行分类的原理
2017-03-12 15:01:06并给出了python的实现代码,但是并没有从原理角度来解释,为什么可以用这个算法来对单词进行分类,以下是我的一些理解,文章末尾会附上python代码(注:本文代码均出自《机器学习实战》,只是为便于描述,实例内容,... -
读书笔记:数据结构与算法分析(Java语言描述)——数据结构概论
2015-08-03 09:21:151.1 什么是数据结构? 逻辑结构: 物理结构(存储结构): 顺序存储结构: 非顺序存储结构: 数据类型:原子类型和结构类型 静态结构和动态结构 数据结构所要研究的内容归为以下3类: 研究数据元素之间... -
python算法有哪些特征
2018-06-01 18:43:24算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制,也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算法有缺陷,或不适合... -
C语言程序设计第五版谭浩强课后答案 第二章《算法--程序的灵魂》习题答案 (大一大二、考研、计算机二级必...
2020-07-12 17:48:22什么是算法?试从日常生活中找3个例子,描述它们的算法2. 什么叫结构化的算法?为什么要提倡结构化的算法?3. 试述3种基本结构的特点,请另外设计两种基本结构(要符合基类结构的特点)。4. 用传统流程图表示求解以下... -
Python 排序算法[一]:令你茅塞顿开,却又匪夷所思
2018-12-19 12:27:06算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。如果一个算... -
稀疏主成分分析算法研究.caj
2020-05-22 12:58:00传统的主成分分析方法是很受欢迎的处理高维数据的降维工具,但其提取的主成分的元素大都是非零的,这就很难去解释主成分对应的具体特征是什么.稀疏主成分分析是在主成分分析的基础上得到的提取稀疏主成分的算法.但稀疏... -
-
分治算法之循环赛程日志表
2017-09-10 15:01:42什么是分治算法? 就是当求解的数据过多,计算的过程过于复杂的情况即可使用分治算法 分治算法的一般步骤: 1.分解:将复杂问题划分为若干同类小问题 2.求解:当子问题足够小时,用简单的方法解决 3.合并:按照求解的要求,...
-
C和C++课程
-
python Flask+scrapy+人工智能 实现高性能搜索引擎
-
重要度引导的抽象艺术风格绘制
-
基于SSM实现的房屋租赁系统【附源码】(毕设)
-
编程基本功:有了范例代码,怎么办?
-
JavaSE之抽象类与接口
-
2021年软考系统规划与管理师-上午历年真题解析视频课程
-
MySQL 备份与恢复详解(高低版本 迁移;不同字符集 相互转换;表
-
GIS地图系统课程设计.pdf
-
世界时区应用-源码
-
深究字符编码的奥秘,与乱码说再见
-
二分查找
-
解决 IDEA Unable to save settings: Failed to save settings. Please restart IntelliJ IDE 问题
-
获取任何一年第一天日期和最后一天日期
-
Commerce:Commerce 2.x开发-源码
-
Dynamic Bone 1.2.2.7z
-
2021-03-03
-
一天学完MySQL数据库
-
自动化测试Python3+Selenium3+Unittest
-
有尘环境多组分气体成分检测系统的设计