KMP 不是魔法：一次失配如何跳过不可能的前缀-平芜编程栈

字符串搜索最怕在重复前缀上反复回退。本文把 KMP 的 next 表解释成可复用的边界证据，使用 Java 完整实现并逐步核对空模式、重叠匹配和 Unicode 字符序列。同时说明边界、复杂度与可复现实验，方便读者直接改造成自己的工具。

一次日志过滤把模式ababaca在长文本中搜索，朴素算法在每次失配后从下一个字符重来，重复比较让延迟随文本放大。KMP 的关键不是更快地比较字符，而是保留已经确认的前缀信息。

线索一：重复前缀留下了什么

模式串自己包含的最长相等前后缀，就是失配后仍然可能对齐的部分。文本指针不回退，模式指针沿前缀函数跳转；像侦探保留排除过的线索，下一轮只检查尚未排除的位置。

线索二：next 表如何办案

令 pi[i] 表示模式前缀 [0…i] 的最长真前后缀长度。计算 pi 时维护 j，失配就令 j=pi[j-1]，直到相等或归零。扫描文本时同样使用 pi，匹配长度达到 m 即记录起点，然后回退到 pi[m-1]，因此可以发现重叠答案。

跟踪一次失配

模式aba搜索ababa：前 3 个字符命中 0，随后 j 回退到 1，文本指针继续前进，最后得到起点 2。若在命中后把 j 置零，会漏掉这个重叠匹配。空模式的约定要在接口层明确，本文返回空列表。

为何不会跳过答案

每次 j 回退都会跳到更短的真前缀，j 不可能无限增加；文本指针只向右移动，所以总比较次数至多 2n。正确性来自：任何可能的下一次匹配，其已匹配部分必须是当前前缀的边界，pi 恰好枚举了最长候选。

把匹配器交给服务

Java 的 char 是 UTF-16 code unit。若业务按 Unicode 码点匹配，应先转为 int 数组；若按字节匹配则显式指定字符集。长文本服务可复用已构建的 pi，避免每个请求重复预处理。

完整可运行代码

importjava.util.*;publicclassKmpDemo{staticint[]prefix(Stringp){int[]pi=newint[p.length()];for(inti=1,j=0;i<p.length();i++){while(j>0&&p.charAt(i)!=p.charAt(j))j=pi[j-1];if(p.charAt(i)==p.charAt(j))j++;pi[i]=j;}returnpi;}staticList<Integer>find(Strings,Stringp){List<Integer>out=newArrayList<>();if(p.isEmpty())returnout;int[]pi=prefix(p);for(inti=0,j=0;i<s.length();i++){while(j>0&&s.charAt(i)!=p.charAt(j))j=pi[j-1];if(s.charAt(i)==p.charAt(j))j++;if(j==p.length()){out.add(i-j+1);j=pi[j-1];}}returnout;}publicstaticvoidmain(String[]args){assertfind("ababa","aba").equals(Arrays.asList(0,2));assertfind("aaaa","aa").equals(Arrays.asList(0,1,2));assertfind("abc","z").isEmpty();System.out.println("kmp tests passed");}}

逐行读代码

prefix 数组只依赖模式串，find 中的 j 表示当前已经匹配的模式长度。while 循环使用 pi[j-1] 而不是 j-1，这是 KMP 能跳跃的核心。命中后立即回退，保证下一次扫描可以复用尾部前缀。

工程扩展

可把 prefix 函数用于周期检测、字符串压缩和增量协议解析。对海量模式可以共享文本扫描框架；模式很多时，Aho-Corasick 更合适。

可复现实验

启用 Java 断言运行java -ea KmpDemo，应输出kmp tests passed。增加模式长度 1、模式比文本长、完全重复和中文字符串，检查结果索引按 UTF-16 单元定义。

复杂度分析

构建 pi 为 O(m)，扫描文本为 O(n)，总时间 O(n+m)，额外空间 O(m)。输出 k 个命中位置还需要 O(k) 空间。

边界条件

空模式、空文本、Unicode 代理项、命中后重叠、模式长度大于文本都必须先约定；索引类型在超长文本中应使用 long 或分段偏移。

常见错误

把失配时 j 直接减一、命中后 j 清零、误用 pi[i] 代替 pi[j-1]，都会导致重复比较或漏报。测试只看是否命中而不看所有起点，也会漏掉重叠案例。

可复制的测试用例

运行三个断言，再随机生成模式和文本，与String.indexOf循环得到的全部起点比较。记录第一处差异的 i、j、pi，能快速定位前缀表错误。

上线前检查

字符模型：明确按 code unit 还是 code point
回退：只沿 pi 链回退
重叠：命中后保留 pi[m-1]
断言：覆盖全部起点

总结

KMP 的价值在于把失败也变成信息。只要保留最长可复用边界，文本指针就不必倒退；这是一种可以迁移到日志、协议和编辑器搜索的思维方式。

标签：KMP字符串匹配前缀函数Java

参考来源

CSDN 数据结构与算法频道
《二分查找：从折半到精准命中》的边界讨论

复盘补充

KMP 的价值在于把失败也变成信息。只要保留最长可复用边界，文本指针就不必倒退；这是一种可以迁移到日志、协议和编辑器搜索的思维方式。 Java 的 char 是 UTF-16 code unit。若业务按 Unicode 码点匹配，应先转为 int 数组；若按字节匹配则显式指定字符集。长文本服务可复用已构建的 pi，避免每个请求重复预处理。