KMP算法

def next(p: str) -> list:
    n = len(p)
    nxt = [0] * n          
    comp = 0               # 当前匹配的前缀长度
    for cur in range(1, n):
        # 不匹配时回溯，直到 comp=0 或 p[cur]==p[comp]
        while comp > 0 and p[cur] != p[comp]:
            comp = nxt[comp - 1]
        if p[cur] == p[comp]:
            comp += 1
            nxt[cur] = comp
        # 如果匹配失败且 comp=0，则 nxt[cur] 保持 0（已初始化）
    return nxt
 
 
def KMP(s: str, p: str) -> int:
    m_next = next(p)    
    sCur, pCur = 0, 0    
    while sCur < len(s) and pCur < len(p):
        if s[sCur] == p[pCur]:
            sCur += 1
            pCur += 1
        elif pCur > 0:
            pCur = m_next[pCur - 1]
        else:
            sCur += 1
 
    return sCur - len(p) if pCur == len(p) else -1
 

第一步：构建 next 数组（前缀函数）

模式串 p = "abcab"，长度 n=5。

初始：

nxt = [0, 0, 0, 0, 0]
comp = 0 (当前匹配的前缀长度)

cur=1 (p[1]=‘b’)

• while: comp=0，跳过
• p[1]=‘b’ vs p[0]=‘a’ → 不相等
• 不进入 if，nxt[1] 保持 0
• 状态：comp=0, nxt=[0,0,0,0,0]

cur=2 (p[2]=‘c’)

• while: comp=0，跳过
• p[2]=‘c’ vs p[0]=‘a’ → 不相等
• nxt[2]=0
• 状态：comp=0, nxt=[0,0,0,0,0]

cur=3 (p[3]=‘a’)

• while: comp=0，跳过
• p[3]=‘a’ vs p[0]=‘a’ → 相等 ✅
• comp 变为 1，nxt[3]=1
• 状态：comp=1, nxt=[0,0,0,1,0]

cur=4 (p[4]=‘b’)

• while: comp=1>0 且 p[4]=‘b’ vs p[1]=‘b’ → 相等？等等，这里 p[comp]=p[1]=‘b’，p[4]=‘b’，所以相等，不进入 while
• p[4]=‘b’ == p[1]=‘b’ ✅
• comp 变为 2，nxt[4]=2
• 最终：comp=2, nxt=[0,0,0,1,2]

最终 next 数组： [0, 0, 0, 1, 2]

含义：

• nxt[0]=0: “a” 无真前后缀
• nxt[1]=0: “ab” 无相等前后缀
• nxt[2]=0: “abc” 无
• nxt[3]=1: “abca” 前缀”a”=后缀”a”
• nxt[4]=2: “abcab” 前缀”ab”=后缀”ab”

---

第二步：KMP 搜索过程

s = "ababcabcab" (索引 09)
p = "abcab" (索引 04)
nxt = [0,0,0,1,2]

初始状态

s: a b a b c a b c a b
p: a b c a b
    ↑
sCur=0, pCur=0

第1轮 (sCur=0, pCur=0)

• s[0]=‘a’ == p[0]=‘a’ ✅
• sCur=1, pCur=1

第2轮 (sCur=1, pCur=1)

• s[1]=‘b’ == p[1]=‘b’ ✅
• sCur=2, pCur=2

第3轮 (sCur=2, pCur=2)

• s[2]=‘a’ vs p[2]=‘c’ ❌ 不匹配
• pCur=2>0 → 跳转：pCur = nxt[2-1] = nxt[1] = 0
• 状态：sCur=2, pCur=0

第4轮 (sCur=2, pCur=0)

• s[2]=‘a’ == p[0]=‘a’ ✅
• sCur=3, pCur=1

第5轮 (sCur=3, pCur=1)

• s[3]=‘b’ == p[1]=‘b’ ✅
• sCur=4, pCur=2

第6轮 (sCur=4, pCur=2)

• s[4]=‘c’ == p[2]=‘c’ ✅
• sCur=5, pCur=3

第7轮 (sCur=5, pCur=3)

• s[5]=‘a’ == p[3]=‘a’ ✅
• sCur=6, pCur=4

第8轮 (sCur=6, pCur=4)

• s[6]=‘b’ == p[4]=‘b’ ✅
• sCur=7, pCur=5

匹配完成

• pCur == len(p) = 5
• 返回起始索引 = sCur - len(p) = 7 - 5 = 2

验证：s[2:7] = “abcab” ✅

---

可视化时间线（关键步骤）

步骤	sCur	pCur	比较	动作	说明
1	0	0	a==a	前进
2	1	1	b==b	前进
3	2	2	a≠c	回退	pCur=nxt[1]=0
4	2	0	a==a	前进
5	3	1	b==b	前进
6	4	2	c==c	前进
7	5	3	a==a	前进
8	6	4	b==b	前进	完成

---

为什么 KMP 比暴力快？

暴力算法在第3步失败后，会从 sCur=1 重新开始匹配。
而 KMP 利用 next 数组知道 p[0:2]="ab" 已经匹配过了，不需要重新比较，直接将 pCur 跳到 0，但 sCur 不动，继续用当前字符 'a' 与 p[0] 比较。

这就避免了重复比较已经匹配过的字符，时间复杂度从 O(n*m) 降为 O(n+m)。

---

title:quote
 
人生处于顺境时能走多快不重要，重要的是遭遇挫折时，能够快速找回自己。
                                                       --KMP