本文是介绍 什么是 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

写这篇文章的原因是发现自己身边一起学习编程的人，自己读得懂程序，但是又写不出代码。

一个程序主要包括以下两方面的信息:

(1〉对数据的描述。在程序中要指定用到哪些数据以及这些数据的类型和数据的组织形式。这就是数据结构(data structure)。

(2)对操作的描述。即要求计算机进行操作的步骤,也就是算法(algorithm)。

数据是操作的对象,操作的目的是对数据进行加.工处理,以得到期望的结果。打个比方,厨师制作菜肴,需要有菜谱,菜谱上一般应说明:①所用配料,指出为了做出顾客所指定的菜肴,应该使用哪些材料﹔②操作步骤,指出有了这些原料,应按什么样的步骤进行加工，才能做出所需的菜肴。

没有原料是无法加工成所需菜肴的,而对同一些原料可以加工出不同风味的菜肴。作为程序设计人员,必须认真考虑和设计数据结构和操作步骤(即算法)。著名计算机科学家沃思(Nikiklaus Wirth)提出一个公式:

算法＋数据结构=程序

…

————摘自谭浩强《C语言程序设计》

什么是算法

做任何事情都有一定的步骤。

例如：

你想从北京去天津开会,首先要去买火车票,然后按时乘坐地铁到北京站,登上火车,到天津站后坐汽车到会场,参加会议;

你要买电视机,先要选好货物,然后开票,付款,拿发票,取货,打车回家;

要考大学,首先要填志愿表,交报名费,拿到准考证,按时参加考试,得到录取通知书,到指定学校报到注册等。

这些步骤都是按一定的顺序进行的,缺一不可,次序错了也不行。从事各种工作和活动,都必须事先想好进行的步骤,然后按部就班地进行,才能避免产生错乱。实际上,在日常生活中,由于已养成习惯,所以人们并没意识到每件事都需要事先设计出“行动步骤”。例如吃饭、上学、打球和做作业等,事实上都是按照一定的规律进行的,只是人们不必每次都重复考虑它而已。

不要认为只有“计算”的问题才有算法。广义地说,为解决一个问题而采取的方法和步骤,就称为“算法”。例如,描述太极拳动作的图解,就是“太极拳的算法”。一首歌曲的乐谱，也可以称为该歌曲的算法,因为它指定了演奏该歌曲的每一个步骤,按照它的规定就能演奏出预定的曲子。

————摘自谭浩强《C语言程序设计》

总结
上面节选了一篇自己看书对算法概念讲解还是比较通俗的一篇文章，自己也是刚刚入门算法不久，教我们C语言的老师说过，如果各种编程语言与程序语法比作武功的“招式”的话，那么数据结构和算法也就比作“内功”。

2.1 程序 = 算法 + 数据结构
一个程序主要包括以下两方面的信息：

数据结构： 对数据的描述。在程序中要指定用到哪些数据，以及这些数据的类型和数据的组织形式。
算法： 对操作的描述。要求计算机进行操作的步骤。


著名计算机科学家沃思提出一个公式：算法 + 数据结构 = 程序 。直到今天，这个公式对于过程化程序来说依然是适用的。

实际上，一个过程化的程序除了以上两个主要因素之外，还应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言表示。因此，算法、数据结构、程序设计方法和语言工具 4 个方面是一个程序设计人员所应具备的知识，在设计一个程序时要综合运用这几方面的知识。在这 4 个方面中，算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。
2.2 什么是算法

广义地说，为解决一个问题而采取的方法和步骤，就称为 “算法” 。
对同一个问题，可以有不同的解题方法和步骤。
为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。

计算机算法可分为两大类别：

数值运算算法： 数值运算的目的是求数值解。由于数值运算往往有现成的模型，可以运用数值分析方法，因此对数值运算的算法的研究比较深入，算法比较成熟。
非数值运算算法： 计算机在非数值运算方面的应用远超在数值运算方面的应用。非数值运算的种类繁多，要求各异，需要使用者参考已有的类似算法，重新设计解决特定问题的专门算法。

算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。算法是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