KMP 字符串匹配 · 分步演示

KMP:失配之后,为什么主指针从来不用往回走

模式串 "ABABCABAB",文本 "ABABDABACDABABCABAB"。 KMP 分两个阶段:先给模式串自己算一张 LPS(最长相同前后缀)表, 再用这张表在匹配失败时直接跳过一大截,不用把文本指针 i 往回退。

阶段一 · LPS(next)数组
当前正在算的位置 i 拿来比较的候选前缀 pat[len]
阶段二 · 用 LPS 表做匹配
先把 LPS 表建完,才开始匹配
正在比较的一对字符 已确认匹配的前缀 完整匹配成功
尚未开始
点击「下一步」开始推演
暴力匹配每次失配都要把文本指针 i 退回去重新试,最坏要 O(n·m) 时间。 KMP 的核心洞察是:模式串自己内部的重复结构(LPS 表)已经告诉我们,失配时该跳到哪, 文本指针 i 全程只往前走,一次都不回退
步骤 0 / 0
推演记录
☕ 如果这篇文章帮到你,可以请作者喝杯咖啡 · 爱发电