Python 算法教程（66）：KMP 字符串匹配算法

Python 算法 2 月前 0 5

前言

KMP 算法是最高效的字符串匹配算法之一，时间复杂度 O(m+n)。

一、问题描述

在文本串 text 中查找模式串 pattern 的所有出现位置。

二、核心思想

利用已匹配信息，避免回溯，通过 next 数组跳过不必要的比较。

三、next 数组构建

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

四、KMP 匹配

def kmpSearch(text, pattern):
    n, m = len(text), len(pattern)
    next = buildNext(pattern)
    j = 0
    result = []
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = next[j-1]
        if text[i] == pattern[j]:
            j += 1
        if j == m:
            result.append(i - m + 1)
            j = next[j-1]
    return result