KMP 算法详解

一、核心原理

1. 问题背景：传统暴力匹配在失配时，主串和模式串都要回溯，效率低下。
2. 优化思路：失配时，主串指针不回溯，仅调整模式串指针，利用已匹配的前缀信息快速定位下次匹配位置。
3. 关键工具：前缀函数（Prefix Function，又称部分匹配表 PMT），用于记录模式串中每个位置的最长前缀（不含最后字符）与后缀（不含首字符）的公共长度。

二、前缀函数（Prefix Function）

• π[0] = 0（单个字符无前缀 / 后缀）
• 对i > 0：
  1. 初始化j = π[i-1]
  2. 若pattern[i] == pattern[j]，则π[i] = j + 1
  3. 否则，令j = π[j-1]，重复步骤 2，直到j = 0；若仍不匹配，则π[i] = 0

三、KMP 匹配流程

1. 预处理模式串，计算前缀函数π
2. 初始化主串指针i = 0，模式串指针j = 0
3. 循环匹配：
   • 若text[i] == pattern[j]，则i++，j++
   • 若j == m（模式串匹配完成），记录匹配位置i - j，令j = π[j-1]继续查找
   • 若失配：
     • 若j > 0，令j = π[j-1]（模式串回退到最长前缀位置）
     • 若j = 0，则i++（主串后移）

四、示例演示

1. 计算前缀函数 π：
   • π[0] = 0（"A"）
   • π[1] = 0（"AB"：前缀 "A"≠后缀 "B"）
   • π[2] = 1（"ABA"：前缀 "A"= 后缀 "A"）
   • π[3] = 2（"ABAB"：前缀 "AB"= 后缀 "AB"）
   • π[4] = 0（"ABABC"：前缀与后缀无匹配）
   • 结果：π = [0,0,1,2,0]
2. 匹配过程：
   • 初始：i=0, j=0，匹配 "A"→i=1, j=1
   • 匹配 "B"→i=2, j=2
   • 匹配 "A"→i=3, j=3
   • 匹配 "B"→i=4, j=4
   • 失配（text [4]="A" vs pattern [4]="C"），j = π[3] = 2
   • 匹配 text [4]="A" vs pattern [2]="A"→i=5, j=3
   • 匹配 text [5]="B" vs pattern [3]="B"→i=6, j=4
   • 匹配 text [6]="C" vs pattern [4]="C"→j=5 == m=5，找到匹配位置6-5=1

五、代码实现

def compute_prefix(pattern):
    m = len(pattern)
    pi = [0] * m
    for i in range(1, m):
        j = pi[i-1]
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j-1]
        if pattern[i] == pattern[j]:
            j += 1
        pi[i] = j
    return pi

def kmp_search(text, pattern):
    n = len(text)
    m = len(pattern)
    if m == 0:
        return []
    pi = compute_prefix(pattern)
    matches = []
    j = 0  # 模式串指针
    for i in range(n):  # 主串指针
        while j > 0 and text[i] != pattern[j]:
            j = pi[j-1]
        if text[i] == pattern[j]:
            j += 1
        if j == m:
            matches.append(i - m + 1)  # 记录匹配起始位置
            j = pi[j-1]  # 继续查找下一个匹配
    return matches

# 示例
text = "ABABABC"
pattern = "ABABC"
print(kmp_search(text, pattern))  # 输出：[1]