KMP算法详解

-1.前置约定
如非特殊说明，以下文字中/(T/)代表主串，/(P/)代表模式串，/(m/)代表主串长度，/(n/)代表模式串长度
真前缀 一个字符串除了它本身之外的前缀。例如，moo 是 moon 的真前缀，moon 却不是。真后缀同理。
“border” 如果字符串 /(a/) 既是 /(b/) 的真前缀，又是 /(b/) 的真后缀，那么我们说 /(a/) 是 /(b/) 的 border。
0.什么是KMP？

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度/(O(m+n)/)。——摘自百度百科

简而言之，它可以在 /(O(m+n)/) 的时间复杂度之内在主串 /(T/) 中找到所有模式串

KMP算法详解最先出现在Python成神之路。