KMP算法

基本概念

KMP 算法（全称 Knuth-Morris-Pratt 算法）：由 Donald Knuth、James H. Morris 和 Vaughan Pratt 三位学者于 1977 年联合提出，并以他们的名字命名。

KMP 算法核心思想：在字符串匹配过程中，当文本串 TT 的某个字符与模式串 pp 发生不匹配时，充分利用已匹配的前缀信息，通过预处理得到的「部分匹配表」（即 next 数组），避免文本指针的回退，从而高效地减少不必要的比较次数，实现快速匹配。

算法步骤

next数组的构造

假设模式串为p。用left表示当前已知的最大相等前后缀的长度，right 表示当前正在处理的字符下标。初始时left = 0,right = 1
比较 $p[left]$ $p [l e f t]$ 和 $p[right]$ $p [r i g h t]$ :
- 如果 $p[left]==p[right]$ ,当前前后缀可以继续延长。此时left+1,将 $next[right]$ 设为left，然后right右移一位。这样, $next[right]$ 就记录了当前最长的相等前后缀长度，方便失配时快速跳转
- 如果 $p[left]!=p[right]$ ，说明当前前后缀不相等。此时left回退到 $next[left-1]$ ，即尝试寻找更短的相等前后缀，直到left=0或再次匹配成功为止。right不动，继续比较
重复上述过程，直到right遍历完整个模式串
最终， $next[j]$ 就表示字串 $p[0:j+1]$ 的最长相等前后缀的长度。这个数组就是KMP算法高效跳转的关键

KMP算法流程

先根据模式串构建其前缀表(即next 数组)
设置两个指针：i指向文本串T的当前位置，j指向模式串p的当前位置，初始均为0
遍历文本串T:
1. 如果 $T[i]==p[j]$ ,则i和j同时右移一位，继续比较下一个字符
2. 如果 $T[i]!=p[j]$ 且j>0，则将j回退到 $next[j-1]$ ，即利用前缀表跳过无效匹配，无需回退i
3. 如果 $T[i]!=p[j]$ 且j=0，则i右移一位，j保持为0
当j等于模式串长度m时，说明已找到完整匹配，返回匹配的起始下标i-m+1
如果遍历完整个文本串仍未找到完整匹配，则返回 -1
该流程通过next数组高效跳转，避免了主串指针的回退，大幅提升了匹配效率

内部实现：

def generateNext(p: str):
	m = len(p)
	next = [0 for _ in range(m)]
	left = 0 
	for right in range(1,m):
		while left>0 and p[left]!=p[right]:
			left= next[left-1]
		if p[left]==p[right]:
			left+=1
		next[right]=left
	return next
def kmp(T:str,p:str)->int:
	n,m=len(T),len(p)
	if m == 0:
		return 0
	next = generateNext(p)
	j= 0
	for i in range(n):
		while j >0 and T[i]!=p[j]:
			j=next[j-1]
		if T[i]==p[j]:
			j+=1
		if j==m:
			return i-m+1
	return -1

复杂度分析：

指标	复杂度	说明
最好时间复杂度	O(n+m)	构造前缀表 O(m)，匹配阶段无回退 O(n)，总计 O(n+m)
最坏时间复杂度	O(n+m)	无论文本和模式内容如何，均为 O(n+m)
平均时间复杂度	O(n+m)	平均情况下同样为 O(n+m)
空间复杂度	O(m)	仅需存储模式串的前缀表（next 数组）

构造前缀表（next）阶段的时间复杂度为 O(m)，其中m是模式串p的长度。
匹配阶段根据前缀表调整位置，文本串指针i不回退，时间复杂度为O(n)，其中n是文本串T的长度。
因此整体时间复杂度为O(n+m)，空间复杂度为 O(m)。与朴素匹配的 O(n×m)相比，有显著提升。
KMP 算法通过预处理模式串的前缀信息，实现文本串指针不回退的高效匹配，是经典的线性时间字符串查找算法。
优点：
- 匹配阶段线性时间，文本指针不回退，效率稳定。
- 仅依赖模式串的前缀表，额外空间开销小（O(m)。
缺点：
- 实现与理解相对复杂，调试成本高于朴素算法。
- 仅适用于精确匹配；包含通配符、编辑距离等需求需用其他算法（如 Aho–Corasick、DP、后缀结构等）

应用场景：

28.找出字符串中第一个匹配项的下标