KMP / 前缀函数字符串匹配

字符串匹配、哈希与回文 · HTML

数学 / 逻辑形态

pi[i] 是 pattern[0..i] 的最长真前缀且同时为后缀的长度；扫描时 j 为当前可复用前缀长度。

识别信号

• 单模式精确匹配
• 需要最坏 O(n+m)
• 要找重叠出现
• 需要 border 或周期信息
• 朴素切片可能 O(nm)

容易误判的相似信号

核心不变量

扫描文本位置前，j 是已处理文本后缀等于模式前缀的最大长度。

状态、转移与处理顺序

Python 骨架

def kmp_find_all(text, pat):
    if not pat: return list(range(len(text)+1))
    pi = [0] * len(pat)
    j = 0
    for i in range(1, len(pat)):
        while j and pat[i] != pat[j]: j = pi[j-1]
        if pat[i] == pat[j]: j += 1
        pi[i] = j
    ans, j = [], 0
    for i, ch in enumerate(text):
        while j and ch != pat[j]: j = pi[j-1]
        if ch == pat[j]: j += 1
        if j == len(pat):
            ans.append(i-len(pat)+1)
            j = pi[j-1]
    return ans

正确性思路

1. pi 记录每个模式前缀可复用的最长 border。
2. 失配后更长候选已被否定，跳到 pi[j-1] 不漏解。
3. j==m 当且仅当完整模式是当前文本后缀。
4. 文本不回退且 j 的总涨落线性。

复杂度

边界条件

• 空模式语义需约定
• 模式长于文本
• 高度重复字符
• 匹配后必须回退找重叠
• 字符规范化可能影响 Unicode 相等

错误模式

选择与排除规则

• 单模式精确匹配且重视最坏界：KMP。
• 大量等长子串比较：rolling hash。
• 多模式：Trie 或多模式自动机。
• 短输入的一次性工程任务可用内置 find。

相关模板

原创微型例子

Recall prompts

• pi[i] 为什么是真前缀？
• 为何回退到 pi[j-1]？
• 完整匹配后如何保留重叠机会？

我的补充