（注：该贴主要运用python实现该算法）
先谈谈KMP算法吧。KMP算法的全称是Knuth-Morris-Pratt 算法，它是用来进行字符串查找，即在某个主字符串里面找到某个特定子字符串。但是好像这个问题也可以直接暴力查找来完成啊，可是暴力查找的的缺点是不可忽视的：它的时间复杂度太高了！一旦遇见长的字符串就会让程序运行时间指数型增长。而用KMP算法可以很好的解决代码的时间复杂度高的问题，它的时间复杂度是线性的，也就是说该算法的时间复杂度取决于两个字符串的长度。
接下来我会对KMP算法完成任务的大概思路进行叙述
首先，我们约定一些符号：S为主字符串，也就是被进行查找的字符串；P为子字符串，也就是需要查找的字符串；next为next数组，里面记录了一些解决任务的关键信息，这里先买一些关子，毕竟比较难解释。
然后就是给定一个主字符串S = ‘ACBACC DBACBACDEA’，子字符串P = ‘ACBACD’，next = [-1, 0, 0, 0, 1, 2]
接着开始比对
如上图，当i = 0，j = 0时，二者相等，所以i和j皆进一位；
当i = 1，j = 1时，二者相等，所以i和j皆进一位；
当i = 2，j = 2时，二者相等，所以i和j皆进一位；
当i = 3，j = 3时，二者相等，所以i和j皆进一位；
当i = 4，j = 4时，二者相等，所以i和j皆进一位；
当i = 5，j = 5时，二者不相等，所以把j = next[j] = 3，i不变；
（箭头表示当前在比较的位置）
当i = 5，j = 2时，二者相等，所以i和j皆进一位；
当i = 6，j = 3时，二者不相等，所以把j = next[j] = 0，i不变；
（箭头表示当前在比较的位置）
当i = 6，j = 0时，二者不相等，所以把j = next[j] = -1，i不变；
当i = 6，j = -1时，此时j为特殊值，所以i和j皆进一位；
当i = 7，j = 0时，二者不相等，所以把j = next[j] = -1，i不变；
当i = 7，j = -1时，此时j为特殊值，所以i和j皆进一位；
当i = 8，j = 0时，二者不相等，所以把j = next[j] = -1，i不变；
当i = 8，j = -1时，此时j为特殊值，所以i和j皆进一位；
（箭头表示当前在比较的位置）
当i = 9，j = 0时，二者相等，所以i和j皆进一位；
当i = 10，j = 1时，二者相等，所以i和j皆进一位；
当i = 11，j = 2时，二者相等，所以i和j皆进一位；
当i = 12，j = 3时，二者相等，所以i和j皆进一位；
当i = 13，j = 4时，二者相等，所以i和j皆进一位；
当i = 14，j = 5时，二者相等，所以i和j皆进一位；
当i = 15，j = 6时，此时检测到j>len(P)了，则跳出循环；
最后返回布尔值，或者返回你想要得到的信息
如此，我们就走完了一次KMP算法，完成了一次任务，得到了正确的结果
通过上面的流程，我们可以得知KMP算法中有一个重要的部分：next数组。
那next数组是什么呢？next数组主要用于存储j位之前的字符串的最长相同前缀和后缀的长度。
（
什么是前缀、后缀呢？"前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。当然，这里指的是在j位之前包括j位的前后缀。
需要注意的是：假如有一个字符串“abcd”，那么其前缀是：a ab abc，其后缀是：bcd cd d。也就是说前后缀是不止一个的。
而前文所说的最长相同前缀和后缀的长度即是指：假若有一个字符串“aabab”，其前缀是：a aa aab aaba，其后缀是：aaba aba ba a，那这个的最长相同前后缀是a，所以该位置对应next数组的位置的值的应该是1。
练习：“abcabx” [0,0,0,1,2,0]
）
这里提供一个代码计算next数组的方法
def get_next(son_str: str) -> list():
"""
获得next数组
参数解释 son_str: 需要求next数组的字符串
返回值: 返回next数组
"""
length = len(son_str)
# 定义next数组
next = length*[None]
next[0] = -1
next[1] = 0
# 计算next数组
k = -1
j = 0
while j < length-1:
if son_str[k] == son_str[j] or k == -1:
j += 1
k += 1
next[j] = k
else:
k = next[k]
return next
这里的next[0] = -1主要是因为方便代码处理j回到0时，发现S[i] != P[j]时，i无法进位的情况（用上面第一个方法求出的next数组也可用，但是具体方法得去搜索了，作者是使用的是代码求出来的那个next数组）
到此，该算法也已经讲得差不多了
下面提供完整的代码
#!/usr/bin/env python
# -*- encoding: utf-8 -*-
'''
@文件名 : KMP.py
@描述 : 实现KMP算法，进行字符串比对
@创建时间 : 2023/09/07/20
@作者 : zrold
@版本 : 1.0
'''
def kmp(farther_str: str, son_str: str) -> bool:
"""
定义KMP算法, 并根据传进来的两个参数来进行比对, 并返回一个布尔值
参数解释: farther_str: 进行比对的主字符串,
son_str: 子字符串
返回值: 返回一个布尔值
"""
# 得到next数组
next = get_next(son_str)
# 匹配字符串
i = 0
j = 0
while i < len(farther_str) and j < len(son_str):
if farther_str[i] == son_str[j] or j == -1:
i += 1
j += 1
else:
j = next[j]
if j >= len(son_str):
return True
else:
return False
def get_next(son_str: str) -> list():
"""
获得next数组
参数解释 son_str: 需要求next数组的字符串
返回值: 返回next数组
"""
length = len(son_str)
# 定义next数组
next = length*[None]
next[0] = -1
next[1] = 0
# 计算next数组
k = -1
j = 0
while j < length-1:
if son_str[k] == son_str[j] or k == -1:
j += 1
k += 1
next[j] = k
else:
k = next[k]
return next
if __name__ == '__main__':
farther_str = input('请输入需要进行对比的主字符串:')
son_str = input('请输入需要在主字符串中找到的子字符串:')
if kmp(farther_str, son_str):
print(f'确实存在"{son_str}"在"{farther_str}"中')
else:
print(f'不存在"{son_str}"在"{farther_str}"中')
标签：数组,son,算法,str,KMP,字符串,next From： https://www.cnblogs.com/zrold/p/17688540.html