KMP 字符串匹配算法原理与 next 数组推导

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，其核心思想是避免主串指针回溯，通过预处理模式串构造 next 数组，使得在发生字符不匹配时，能够快速调整模式串的匹配位置。

代码实现

def compute_next(pattern):
    """计算模式串的 next 数组"""
    m = len(pattern)
    next_arr = [-1] * m  # 初始化 next 数组，第一个元素为 -1
    j = -1  # 指向前缀末尾（初始为 -1）
    for i in range(1, m):  # i 指向后缀末尾
        while j != -1 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

def kmp_search(text, pattern):
    """KMP 算法主函数：返回模式串在主串中首次出现的起始下标，未找到返回 -1"""
    if not pattern:
        return 0
    n, m = len(text), len(pattern)
    next_arr = compute_next(pattern)
    j = -1  # 模式串匹配指针（当前已匹配到的位置）
    for i in range(n):  # 遍历主串
        while j != -1 and text[i] != pattern[j + 1]:
            j = next_arr[j]  # 失配时利用 next 跳转
        if text[i] == pattern[j + 1]:
            j += 
         j == m - :  
             i - m +   
     -  


text = 
pattern = 
next_table = compute_next(pattern)
(, next_table)  
pos = kmp_search(text, pattern)
()