KMP 字符串匹配算法详解 - Python 实现教程

AI技术 4 小时前 0 2

作者：小弟
发布时间：2026 年 3 月 25 日
标签：KMP, 字符串匹配，算法，Python

📖 前言

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，由 Donald Knuth、Vaughan Pratt 和 James H. Morris 于 1977 年联合发表。相比暴力匹配算法，KMP 算法的时间复杂度从 O(mn) 优化到了 O(m+n)，其中 m 是文本串长度，n 是模式串长度。

本文将带你从零开始理解 KMP 算法的核心思想，并用 Python 实现完整的代码。

🎯 问题定义

字符串匹配问题：给定一个文本串 text 和一个模式串 pattern，判断 pattern 是否是 text 的子串，如果是，返回第一次出现的位置。

示例：

text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
# 期望返回：10（pattern 在 text 中第一次出现的位置）

🔍 暴力匹配算法

算法思路

从文本串的每个位置开始，逐个字符与模式串比较，如果匹配失败，文本串指针回退到下一个位置，模式串指针重置为 0。

Python 实现

def brute_force_match(text: str, pattern: str) -> int:
    """暴力字符串匹配算法"""
    n, m = len(text), len(pattern)
    
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:
            return i  # 匹配成功，返回起始位置
    
    return -1  # 匹配失败

# 测试
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(f"暴力匹配结果：{brute_force_match(text, pattern)}")  # 输出：10

时间复杂度

最坏情况下时间复杂度为 O(m × n)。存在大量"回退"操作，导致效率低下。

💡 KMP 算法核心思想

关键洞察

当匹配失败时，模式串已经有一部分与文本串匹配成功了。这部分已匹配的子串中，可能包含前缀和后缀相同的部分。我们可以利用这个信息，将模式串"滑动"到一个更优的位置，而不是简单地回退。

示例图解

文本串：A B C A B C A B D A B C
                ↑
模式串：A B C A B C A B E
                ↑
              匹配失败（D ≠ E）

已匹配部分："ABCABCAB"
- 最长相同前后缀："ABCAB"（长度 5）
- 模式串可以滑动到：

文本串：A B C A B C A B D A B C
                    ↑
模式串：            A B C A B C A B E
                    ↑
（直接从第 5 个位置继续比较，不需要回退文本串指针）

🔧 部分匹配表（Next 数组）

什么是 Next 数组？

Next 数组（也叫部分匹配表 PMT）是 KMP 算法的核心。对于模式串的每个位置 i，next[i] 表示：pattern[0:i+1] 这个子串中，最长相同前后缀的长度。

示例计算

以模式串 "ABABCABAB" 为例：

位置 i	子串	next[i]
0	A	0
1	AB	0
2	ABA	1
3	ABAB	2
4	ABABC	0
5	ABABCA	1
6	ABABCAB	2
7	ABABCABA	3
8	ABABCABAB	4

Next 数组计算代码

def compute_next(pattern: str) -> list:
    """
    计算 KMP 算法的 Next 数组（部分匹配表）
    
    Args:
        pattern: 模式串
    
    Returns:
        next 数组，next[i] 表示 pattern[0:i+1] 的最长相同前后缀长度
    """
    n = len(pattern)
    next_arr = [0] * n
    
    j = 0  # 前缀指针
    for i in range(1, n):  # i 是后缀指针
        # 如果当前字符不匹配，回退 j 指针
        while j > 0 and pattern[i] != pattern[j]:
            j = next_arr[j - 1]
        
        # 如果当前字符匹配，前缀长度 +1
        if pattern[i] == pattern[j]:
            j += 1
        
        # 记录当前位置的最长相同前后缀长度
        next_arr[i] = j
    
    return next_arr

# 测试
pattern = "ABABCABAB"
next_arr = compute_next(pattern)
print(f"模式串：{pattern}")
print(f"Next 数组：{next_arr}")  # 输出：[0, 0, 1, 2, 0, 1, 2, 3, 4]

🚀 KMP 算法完整实现

主算法代码

def kmp_search(text: str, pattern: str) -> int:
    """
    KMP 字符串匹配算法
    
    Args:
        text: 文本串
        pattern: 模式串
    
    Returns:
        模式串在文本串中第一次出现的位置，如果不存在返回 -1
    """
    if not pattern:
        return 0
    
    # 计算 next 数组
    next_arr = compute_next(pattern)
    
    j = 0  # 模式串指针
    for i in range(len(text)):  # i 是文本串指针
        # 如果当前字符不匹配，回退 j 指针
        while j > 0 and text[i] != pattern[j]:
            j = next_arr[j - 1]
        
        # 如果当前字符匹配，模式串指针 +1
        if text[i] == pattern[j]:
            j += 1
        
        # 如果模式串完全匹配，返回起始位置
        if j == len(pattern):
            return i - j + 1
    
    return -1  # 匹配失败

# 测试
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
result = kmp_search(text, pattern)
print(f"KMP 匹配结果：{result}")  # 输出：10
print(f"验证：text[{result}:{result+len(pattern)}] = {text[result:result+len(pattern)]}")

查找所有匹配位置

def kmp_find_all(text: str, pattern: str) -> list:
    """
    使用 KMP 算法查找模式串在文本串中的所有出现位置
    
    Args:
        text: 文本串
        pattern: 模式串
    
    Returns:
        所有匹配位置的列表
    """
    if not pattern:
        return []
    
    next_arr = compute_next(pattern)
    positions = []
    
    j = 0
    for i in range(len(text)):
        while j > 0 and text[i] != pattern[j]:
            j = next_arr[j - 1]
        
        if text[i] == pattern[j]:
            j += 1
        
        if j == len(pattern):
            positions.append(i - j + 1)
            j = next_arr[j - 1]  # 继续查找下一个匹配
    
    return positions

# 测试
text = "ABABDABACDABABCABAB"
pattern = "ABA"
positions = kmp_find_all(text, pattern)
print(f"模式串 '{pattern}' 在文本串中的所有位置：{positions}")  # 输出：[0, 2, 10, 16]

⏱️ 时间复杂度分析

Next 数组计算

时间复杂度：O(n)，其中 n 是模式串长度
空间复杂度：O(n)，存储 next 数组

KMP 匹配过程

时间复杂度：O(m)，其中 m 是文本串长度
空间复杂度：O(n)，存储 next 数组

总体复杂度

时间复杂度：O(m + n)
空间复杂度：O(n)

📝 完整代码

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
KMP 字符串匹配算法完整实现
作者：小弟
日期：2026 年 3 月 25 日
"""


def compute_next(pattern: str) -> list:
    """计算 KMP 算法的 Next 数组（部分匹配表）"""
    n = len(pattern)
    next_arr = [0] * n
    j = 0
    for i in range(1, n):
        while j > 0 and pattern[i] != pattern[j]:
            j = next_arr[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        next_arr[i] = j
    return next_arr


def kmp_search(text: str, pattern: str) -> int:
    """KMP 字符串匹配算法，返回第一次出现的位置"""
    if not pattern:
        return 0
    next_arr = compute_next(pattern)
    j = 0
    for i in range(len(text)):
        while j > 0 and text[i] != pattern[j]:
            j = next_arr[j - 1]
        if text[i] == pattern[j]:
            j += 1
        if j == len(pattern):
            return i - j + 1
    return -1


def kmp_find_all(text: str, pattern: str) -> list:
    """使用 KMP 算法查找所有匹配位置"""
    if not pattern:
        return []
    next_arr = compute_next(pattern)
    positions = []
    j = 0
    for i in range(len(text)):
        while j > 0 and text[i] != pattern[j]:
            j = next_arr[j - 1]
        if text[i] == pattern[j]:
            j += 1
        if j == len(pattern):
            positions.append(i - j + 1)
            j = next_arr[j - 1]
    return positions


if __name__ == "__main__":
    # 测试用例 1
    text1 = "ABABDABACDABABCABAB"
    pattern1 = "ABABCABAB"
    print(f"测试 1: text = '{text1}'")
    print(f"       pattern = '{pattern1}'")
    print(f"       匹配位置：{kmp_search(text1, pattern1)}")
    print()
    
    # 测试用例 2
    text2 = "AABAACAADAABAABA"
    pattern2 = "AABA"
    print(f"测试 2: text = '{text2}'")
    print(f"       pattern = '{pattern2}'")
    print(f"       所有位置：{kmp_find_all(text2, pattern2)}")
    print()
    
    # 测试用例 3（中文）
    text3 = "今天天气很好，今天心情也不错"
    pattern3 = "今天"
    print(f"测试 3: text = '{text3}'")
    print(f"       pattern = '{pattern3}'")
    print(f"       所有位置：{kmp_find_all(text3, pattern3)}")

🎓 关键要点总结

核心思想：利用已匹配部分的信息，避免文本串指针回退
Next 数组：记录模式串每个位置的最长相同前后缀长度
时间复杂度：O(m + n)，优于暴力匹配的 O(mn)
应用场景：文本搜索、DNA 序列匹配、入侵检测系统等

📚 扩展阅读

BM（Boyer-Moore）算法：另一种高效的字符串匹配算法
Trie 树：多模式串匹配的数据结构
AC 自动机：多模式串匹配的经典算法
正则表达式：更强大的模式匹配工具

💬 结语

KMP 算法是字符串匹配领域的经典算法，理解它不仅能帮助你解决实际问题，更能培养"利用历史信息优化算法"的思维方式。希望这篇教程能帮你彻底掌握 KMP 算法！

有问题欢迎在评论区留言讨论！

本文代码已在 Python 3.x 环境下测试通过。

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。