核心概述
KMP（Knuth–Morris–Pratt）算法用于在文本串中高效查找单一模式串的全部出现位置，通过预处理失配函数避免文本指针回溯，时间复杂度 O(n+m)。
原文引述
Description: Find all occurrences of pattern p in text s in O(|s|+|p|) using prefix function (failure function). No backtracking on the text; useful for single pattern matching. Time: O(|s|+|p|) Status: tested ——摘自本节点现有英文注释
展开阐述
-
定义与背景
- 目标：在文本 s 中寻找模式 p 的所有匹配起点。
- 思想：利用模式自身的最长真前后缀信息（next/pi 数组）在失配时跳转，避免回退文本索引。
-
接口/字段/数据结构与输入输出语义（按仓库约定）
- 典型接口（据约定风格）：
- vector
prefixFunction(const string& p) - 返回模式串 p 的 next（或 pi）数组。
- vector
kmpSearch(const string& s, const string& p) - 返回所有起始位置 i（0-index）使得 s[i..i+|p|−1] == p。
- 可选：int kmpCount(const string& s, const string& p) 统计出现次数。
- vector
- 输出语义：
- kmpSearch 返回升序的起始位置列表；无匹配返回空。
- 典型接口（据约定风格）：
-
核心流程与关键要点
- 预处理模式串 p 计算 next 数组：
- next[0]=0；
- 对 i=1..|p|−1：
- j = next[i−1]；
- while (j>0 && p[i]!=p[j]) j = next[j−1]；
- 若 p[i]==p[j] 则 j++；
- next[i]=j。
- 语义：next[i] 为 p[0..i] 的最长真前缀且同时为后缀的长度。
- 匹配阶段（扫描文本 s）：
- 维护当前已匹配长度 j；
- 对每个字符 s[i]：
- while (j>0 && s[i]!=p[j]) j = next[j−1]；
- 若 s[i]==p[j] 则 j++；
- 若 j==|p|：
- 记录匹配位置 i−|p|+1；
- j = next[j−1]（继续寻找重叠匹配）。
- 正确性要点与不变式：
- 不回退文本指针；不变式为“已匹配前缀长度 j 的后缀等于 p 的前缀”。
- 数值/实现注意：
- 字符比较为等值关系；支持一般字符集。
- 返回索引约定为 0-index，注意与题面一致。
- 预处理模式串 p 计算 next 数组：
-
复杂度与边界条件
- 复杂度：预处理 O(|p|)，匹配 O(|s|)，总 O(|s|+|p|)；空间 O(|p|)。
- 边界：空模式（通常定义为匹配所有位置或直接返回空，依实现约定）；空文本返回空。
- 常见变体/扩展：
- 循环串匹配可在 p+p 中查找 s（注意长度截断）。
- 与 Z 函数等价用于单模式匹配（见 126-字符串-Z函数）。
-
与相邻技术的取舍对比
- 多模式匹配建议使用 118-字符串-AC自动机。
- 基于哈希的等价判定参见 119-字符串-字符串哈希（概率正确），与确定性匹配可互补。
- 与后缀结构：静态全局子串关系分析可参考 124-字符串-后缀数组、125-字符串-后缀树。