代码与动画 KNUTH–MORRIS–PRATT
KMP 字符串匹配.
利用最长相等前后缀表，在失配时复用已匹配的字符。
时间 O(n + m)空间 O(m)返回首次匹配下标
原理与执行逻辑
预先计算模式串每个前缀的最长相等真前后缀长度 LPS。匹配失配时，利用已经相等的部分跳转模式指针，避免重新检查整段文本。
执行步骤
- 逐项构建 LPS，前后缀失配时沿已有 LPS 回退长度。
- 用 i 扫描文本、j 扫描模式，相等时两个指针前进。
- 失配且 j > 0 时令 j = LPS[j - 1]，文本 i 保持不动；j = 0 时才增加 i。
- j 达到模式长度时返回 i - j，文本耗尽仍未匹配时返回 -1。
关键理解
真前后缀不包含字符串自身。跳转后的前缀与已匹配片段的后缀相同，可以复用匹配结果，文本指针不会向左移动。
简短示例
模式 ABABC 的 LPS 为 [0, 0, 1, 2, 0]；匹配了 ABAB 后失配，j 从 4 跳到 2，保留后缀 AB 的匹配信息。
代码与执行动画
STEP 0 / 27function kmp(text, pattern) { const lps = Array(pattern.length).fill(0); for (let i = 1, len = 0; i < pattern.length;) { if (pattern[i] === pattern[len]) lps[i++] = ++len; else if (len > 0) len = lps[len - 1]; else lps[i++] = 0; } let i = 0, j = 0; while (i < text.length) { if (text[i] === pattern[j]) { i++; j++; } else if (j > 0) j = lps[j - 1]; else i++; if (j === pattern.length) return i - j; } return -1;}上行文本 · 中行模式 · 下行LPS
当前数据正在操作已访问 / 命中标记 / 指针
0
初始化 LPS
LPS 保存每个模式前缀的最长相等真前后缀长度。
配置演示数据
应用后重新生成执行过程，可单步观察结果。
KMP 字符串匹配的操作规则
先构建 LPS 表，再匹配文本。动画三行分别为文本、模式和 LPS；失配时文本指针不回退。
对应题目与扩展练习
观察执行过程后，按题目约束调整输入、返回值与实现。链接打开官方题目页面。
直接对应首次匹配下标，可使用 KMP 完成。