手写KMP字符串匹配算法

题目描述

KMP算法（Knuth-Morris-Pratt算法）是一种高效的字符串匹配算法，用于在一个主串（文本串）中查找一个模式串（子串）出现的位置。相比暴力匹配算法的O(m×n)时间复杂度，KMP算法能够在O(m+n)时间内完成匹配，其中m是模式串长度，n是主串长度。

核心思想

KMP算法的核心在于利用已匹配部分的信息，避免主串指针的回退，从而提高匹配效率。这是通过一个"部分匹配表"（也称为next数组）实现的，这个表记录了模式串每个位置之前的最长相同前后缀长度。

详细步骤解析

步骤1：理解前后缀概念

• 前缀：包含第一个字符但不包含最后一个字符的所有连续子串
• 后缀：包含最后一个字符但不包含第一个字符的所有连续子串
• 例子：对于字符串"ABAB"
  • 前缀：A, AB, ABA
  • 后缀：B, AB, BAB
  • 最长相同前后缀：AB（长度2）

步骤2：构建next数组

next数组是KMP算法的核心，它记录了当匹配失败时，模式串应该回退到的位置。

构建规则：

• next[0] = -1（第一个字符匹配失败，主串指针向后移动）
• 对于i>0，next[i]表示模式串[0, i-1]的最长相同前后缀长度

构建过程示例（模式串："ABABC"）：

高效构建算法：

初始化：next[0] = -1, i = 0, j = -1
while i < 模式串长度-1:
    if j == -1 或 pattern[i] == pattern[j]:
        i++, j++
        next[i] = j
    else:
        j = next[j]

步骤3：实现KMP匹配过程

主串指针i = 0
模式串指针j = 0
while i < 主串长度:
    if j == -1 或 主串[i] == 模式串[j]:
        i++, j++
    else:
        j = next[j]  // 回退模式串指针
    
    if j == 模式串长度:
        找到匹配，返回i-j

完整代码实现

def build_next(pattern: str) -> list:
    """
    构建KMP算法的next数组
    """
    n = len(pattern)
    next_arr = [0] * n
    next_arr[0] = -1
    
    i, j = 0, -1
    while i < n - 1:
        if j == -1 or pattern[i] == pattern[j]:
            i += 1
            j += 1
            next_arr[i] = j
        else:
            j = next_arr[j]
    return next_arr

def kmp_search(text: str, pattern: str) -> int:
    """
    使用KMP算法在主串中查找模式串
    返回第一个匹配位置，未找到返回-1
    """
    if not pattern:
        return 0
    
    n, m = len(text), len(pattern)
    if m > n:
        return -1
    
    next_arr = build_next(pattern)
    
    i, j = 0, 0
    while i < n and j < m:
        if j == -1 or text[i] == pattern[j]:
            i += 1
            j += 1
        else:
            j = next_arr[j]
    
    if j == m:
        return i - j
    return -1

# 示例
text = "ABABABABCABABD"
pattern = "ABABC"
result = kmp_search(text, pattern)
print(f"模式串'{pattern}'在主串中的起始位置: {result}")  # 输出: 2

时间空间复杂度分析

• 时间复杂度：O(m+n)
  • 构建next数组：O(m)，m为模式串长度
  • 匹配过程：O(n)，n为主串长度
• 空间复杂度：O(m)，用于存储next数组

实际应用场景

1. 文本编辑器中的查找功能
2. DNA序列匹配
3. 搜索引擎的关键词匹配
4. 防病毒软件的病毒特征码扫描
5. 版本控制系统中的差异比较

优化变体

1. next数组优化：在处理像"AAAAAB"这样的模式串时，可以进一步优化
2. Boyer-Moore算法：更适合英文文本搜索
3. Sunday算法：在某些情况下更高效

面试要点

1. 必须能手写next数组的构建过程
2. 理解KMP相比暴力匹配的优势
3. 能够分析最坏情况的时间复杂度
4. 了解实际应用中的局限性
5. 掌握优化版本的实现

通过理解KMP算法，你不仅能掌握高效的字符串匹配技术，还能深入理解"利用已有信息避免重复比较"这一重要的算法设计思想。