KMP算法主要是用来解决串的匹配问题,为此,在学习KMP之前我们先来了解一下串的相关知识。
字符串的匹配问题，也就是查找一个字符串（称为模式串pattern）在另一个字符串（称为文本串text）中的位置。
'''
Brute Force 蛮力法匹配字符串
'''
class BruteForce():
@staticmethod
def indexOf(text: str, pattern: str) -> int:
n=len(text)
m=len(pattern)
pi,ti=0,0#pi、ti分别指向正在进行比较的元素索引
#ti-pi<=n-m 防止末尾长度不够仍进行匹配
while pi<m and ti-pi<=n-m:
if text[ti]==pattern[pi]:
pi+=1
ti+=1
else:
#text使用下一个元素比较，pattern从再来
ti+=1
pi=0
return ti-pi if pi==m else -1
if __name__=='__main__':
text='ABCSBEFG'
pattern='SBE'
print(BruteForce.indexOf(text,pattern))
显然，BruteForce算法的时间复杂度为O(m*n)。
下面我们再看一个例子，通过对比BruteForce与KMP的差异来了解KMP。
相比之前，pattern在text中进行匹配的位置只移动了一个字符，且接下来的匹配也很可能是无效的，但如果使用KMP算法，pattern字符串将移动尽可能多的字符，并保证pattern中位于下一个进行比较的字符之前的子串都和text匹配。
对于字符串ABCHAB，它的最大公共子串长度为2。
对于字符串ABCHA，它的最大公共子串长度为1。
对于字符串ABCH，它的最大公共子串长度为0。
下面我们回到场景中，当pattern在字符Y处匹配失败，如果我们知道Y之前的字符串ABCHABC的最大真前缀真后缀公共子串长度L（此处L为3），就可以直接将pi（pattern进行比较的字符的索引）移动到L，来对索引3也就是第四个字符进行比较（前3个字符一定与text匹配）,如下图所示。
那么为什么可以这么做，为什么中间跳过的一些位置不需要进行比较？这其实是ABCHABC的最大公共子串长度L在起作用。当我们再次用BruteForce的方式对pattern进行逐字符的移动，并与text进行匹配时，我们会惊奇地发现，原来一开始我们都在进行pattern（准确地说是pattern中的子串ABCHABC）的等长前缀与后缀的匹配，见下图。
在BruteForce中的第一次移动pattern，其实是字符Y前的子串ABCHABC中的前缀与后缀的匹配，由于我们知道最长匹配长度为3，当前长度为6的前后缀是一定不会匹配的，换而言之，这是一次无效的匹配。
那么我们按BruteForce让pattern再次移动一个字符，但匹配一开始进行的仍旧是前后缀匹配，匹配失败。
随着pattern的移动前后缀进行匹配的长度在不断减小，但仍旧大于最长公共子串的长度，匹配失败。
经过多次无效的匹配，BruteForce终于将pattern移动到与KMP相同的位置，但想让pi的位置与KMP相同，还需要对前后缀字符进行3次比较，才能到达H，哪怕我们知道最长公共子串长度为3，这些比较一定会相等。
相信到这里，我们已经可以感受到KMP相对于BruteForce的迅速，而且我们也知道KMP在失配的时候，需要得到pattern失配字符（第一个匹配失败的字符）前的子串的最大真前缀真后缀公共子串数。而pattern可能在任何一个字符处失配，为此我们需要保存每一个前缀子串的最大公共子串数于数组next中，这也就是next数组的由来，下面是next数组含义的简单示例。
可以注意到next[0]的取值为-1，与0一样表示不存在公共子串，但是有着不同的含义，通过以下的例子说明。
假如我们已经得到了pattern的next数组（next数组的构造在下面阐述），那么就可以进行KMP算法的字符串匹配，在此我们需要明确一点，什么时候我们需要用到next数组，其实是某个字符失配的时候，如下图。
当pattern中的字符Y失配，我们将通过next[7]得到配对成功字符串ABCHABC的最大前后缀子串长度L=3，再对pattern的位置进行移动，可以发现L指向的索引恰好就是下一个需要进行比较字符的索引，所以我们只需要让pi=next[pi]=3即可。
下面对H与G进行比较，发现依旧失配，按KMP算法，我们需要再次取出next[pi]作为下一次比较的索引。查阅next数组我们发现next[3]=0，这意味着前缀ABC不存在前后缀公共子串，这也意味着我们要从头开始，让索引为0的字符与G进行比较。
此时A与G依旧不匹配，按KMP算法我们还是要取next[0]作为下一次进行比较字符的索引，但倘若next[0]=0，只会进入一个不断用pattern[0]进行比较的死循环，那么先不考虑next[0]的取值，在蛮力解法下遇到这种情况我们会做什么呢，显然我们会让text进行比较的位置移动一个字符，pi=0保持不变，在下一个字符再开始比较，用代码表示为pi=0,ti+=1。那么在KMP中，我们也应该进行这样一个操作。
所以我们让next[0]等于一个负数来与0区分，表示使用pattern[0]进行比较后仍旧不匹配，需要让text移动一个字符的操作，而不是简单地移动pattern进行比较字符的位置，让pi=next[pi]（负数无法作为数组的索引）。至于为什么要选择-1，这是因为选择了-1后，这个让text移动一个字符的操作，可以与当前位置的两个字符匹配时的后续操作相同，用同一段代码表示。当两个字符匹配时，我们需要进行什么操作？其实是分别让text和pattern使用下一个字符比较，翻译成代码就是pi+=1,ti+=1，当pi=-1时，这段自加的代码代码不就等价于pi=0,ti+=1吗，所以下面我们就先来完成KMP的主体代码。
class KMP():
@staticmethod
def indexOf(text:str,pattern:str)->int:
n=len(text)
m=len(pattern)
if n==0 or m==0:
return -1
#text:abcdefgh 8 pattern:def 3
pi,ti=0,0#指向进行比较的指针
next=KMP.next(pattern)
while pi<m and ti-pi<=n-m:
if pi<0 or text[ti]==pattern[pi]:
pi+=1
ti+=1
else:
pi=next[pi]
#通过pi是否检索完所有字符来判断是否查找到
return ti-pi if pi==m else -1
@staticmethod
def next(pattern:str)->[]:
...#待完成
return next
那么如何构造pattern字符串的next数组？对此当然可以使用遍历的方法，对每个子串的前后缀进行比较，但这样显然效率不高。在此我们使用dp的方法来构造next数组（也就是用前子串的next值来推导下一个next），下面通过几个例子来说明。
假如我们已经知道了next数值中0到i-1的数值，我们应该如何得到next[i]？先来看next[i]的定义：字符A前字符串的最大真前后缀公共字串的长度；再来看next[i-1]：字符T前字符串的最大真前后缀公共字串的长度，在图中显示绿色。而next[i]定义中使用的字符串相比next[i-1]就多了末尾一个，如果这个多出的字符和next[i-1]指向的字符相等，那么next[i]显然等于next[i-1]+1，如下图所示。
但倘若这两个字符串不相等，又该如何求得next[i]？下面我们先假设字符串pattern[0,i-1]的公共前后缀存在（但一定包含在绿色字符串内），如下图蓝色括号所示。
如果蓝色括号中的字符串相等，势必要有两个前提，第一是括号中左半段蓝色的字符相等，二是括号中最后一个字符相等。可以发现，括号中的左半段，其实是绿色字符串的前后缀，既然前后缀要相等，我们就可以通过索引preNext=next[i-1]来获取绿色字符串的最大前后缀next[preNext]，来保证括号中的左半段字符相等，再通过比较最后一个字符，来判断能否在此得出next[i]的值。哪怕此时仍旧不相等，我们也可以再到蓝色字符串的公共前后缀进行比较。
如果括号中的最后一个字符一直不相等，最后的比较势必会进行到第一个字符（next值为0）与最后一个字符，此时如果还是不相等，preNext的值将等于-1（一开始就设置next[0]=-1)，表明使用第一个字符进行比较仍旧不相等，此时应该next[i]设置为0，与上相同，该情况的代码依旧与字符相同合并为pi+=1、preNext+=1（-1+1=0），下面是构造next数组的代码。
@staticmethod
def next(pattern:str)->[]:
m=len(pattern)
pi=0
next=[0]*m
preNext=-1
next[0]=-1
#pi的取值为[0,m-2]，依次为next[1,m-1]赋值
while pi<m-1:
#preNext为前一位的next值
if preNext<0 or pattern[preNext]==pattern[pi]:
pi+=1
preNext+=1
next[pi]=preNext
else:
preNext=next[preNext]
return next
但事实上，这样构造完成的next数组还有一些不足之处。
当末尾元素相等时，next[i]=next[i-1]+1，但如果此时next[i]处的元素与i处的元素相等，就可能会出现无效的比较，因为当i处的字符失配时，pattern将跳转至next[i]处进行比较，而pattern[i]等于pattern[next[i]]，比较一定会失败。
为了避免无效比较，我们需要找到第一个不与该字符相等的索引位置，而操作其实很简单，只需要对next[i]赋值时需要加入一层判断，即pattern[next[i]]是否与pattern[i]相等，若相等则让next[i]=next[next[i]]。由于next[i]是从1到n-1从小到大开始构造的，这些相等字符中的第一个，它的next一定指向-1或者不同的字符，且这个不同字符的索引会随着之后的next[next[i]]操作不断向后传递，这点我们可以通过观察示例字符串优化前后的next数组得到。
下面是优化后的next数组代码。
@staticmethod
def next(pattern:str)->[]:
m=len(pattern)
pi=0
next=[0]*m
preNext=-1
next[0]=-1
while pi<m-1:
if preNext<0 or pattern[preNext]==pattern[pi]:
pi+=1
preNext+=1
if pattern[pi]==pattern[preNext]:
next[pi]=next[preNext]
else:
next[pi]=preNext
else:
preNext=next[preNext]
return next
整体代码。
class KMP():
@staticmethod
def indexOf(pattern:str,text:str):
m=len(pattern)
n=len(text)
next=KMP.next(pattern)
pi,ti=0,0
while pi<m and ti-pi<=n-m:
if pi<0 or pattern[pi]==text[ti]:
ti+=1
pi+=1
else:
pi=next[pi]
return ti-pi if pi==m else -1
@staticmethod
def next(pattern:str)->[]:
m=len(pattern)
pi=0
next=[0]*m
preNext=-1
next[0]=-1
while pi<m-1:
if preNext<0 or pattern[preNext]==pattern[pi]:
pi+=1
preNext+=1
if pattern[pi]==pattern[preNext]:
next[pi]=next[preNext]
else:
next[pi]=preNext
# next[pi]=preNext
else:
preNext=next[preNext]
return next
if __name__=='__main__':
pattern='cdefg'
text='abcdefgabcabd'
result=KMP.indexOf(pattern,text)
print(result)
由比较的示例图中的字符比较次数（绿色部分）我们可以看出kmp比较的时间复杂为O(n)（n为文本串text的长度），而构造next数组的时间复杂度为O(m)（m为模式串pattern的长度），所以总体时间复杂度为O(n+m)。