KMP字符串匹配算法

题目描述
给定一个文本串text和一个模式串pattern，要求在text中查找pattern首次出现的位置。KMP算法通过预处理模式串构建next数组，利用匹配失败时的已知信息避免回溯，将时间复杂度优化到O(n+m)。

核心思想
当出现字符不匹配时，模式串可以向右滑动多位（而不仅是1位），利用已匹配部分的信息避免文本串指针回溯。关键是通过next数组记录模式串的"自匹配"信息。

next数组详解
next[i]表示模式串p[0:i]中，使得前k个字符与后k个字符相等的最大的k（k < i），即最长相同前后缀的长度。

构建next数组的步骤

1. 初始化：next[0] = -1（特殊标记），i=0，j=-1
2. 循环处理每个位置i（从1到m-1）：
   • 当j >= 0且p[i] != p[j+1]时，令j = next[j]（回退）
   • 如果p[i] == p[j+1]，则j++（扩展匹配长度）
   • 设置next[i] = j

示例：模式串"ABABC"

• i=0: next[0]=-1, j=-1
• i=1: p[1]=B != p[0]=A → j=-1, next[1]=-1
• i=2: p[2]=A == p[0]=A → j=0, next[2]=0
• i=3: p[3]=B == p[1]=B → j=1, next[3]=1
• i=4: p[4]=C != p[2]=A → j=next[1]=-1 → p[4]=C != p[0]=A → next[4]=-1
  最终next数组：[-1, -1, 0, 1, -1]

匹配过程

1. 初始化：i=0（文本串指针），j=-1（模式串指针）
2. 遍历文本串：
   • 当j >= 0且text[i] != pattern[j+1]时，j = next[j]（利用next数组跳转）
   • 如果text[i] == pattern[j+1]，则j++
   • 如果j达到模式串末尾，返回匹配位置i - j
   • i指针始终向前移动

完整代码实现

def kmp(text, pattern):
    if not pattern:
        return 0
    
    n, m = len(text), len(pattern)
    next_arr = build_next(pattern)
    
    j = -1  # 模式串指针
    for i in range(n):  # 文本串指针单向移动
        while j >= 0 and text[i] != pattern[j+1]:
            j = next_arr[j]  # 不匹配时回退
            
        if text[i] == pattern[j+1]:
            j += 1
            
        if j == m - 1:  # 完全匹配
            return i - j
    
    return -1

def build_next(pattern):
    m = len(pattern)
    next_arr = [-1] * m
    j = -1  # 指向前缀末尾
    
    for i in range(1, m):  # i指向后缀末尾
        while j >= 0 and pattern[i] != pattern[j+1]:
            j = next_arr[j]  # 回退到前一个匹配位置
            
        if pattern[i] == pattern[j+1]:
            j += 1
            
        next_arr[i] = j
    
    return next_arr

算法分析

• 时间复杂度：O(n+m)，文本串和模式串各遍历一次
• 空间复杂度：O(m)，用于存储next数组
• 优势：避免文本串指针回溯，适合处理流式数据

实际应用场景

1. 文本编辑器中的查找功能
2. DNA序列匹配
3. 网络数据包的模式识别
4. 编译器的词法分析