LeetCode 28 这道题我很久之前就刷过当时只把它当成一道普通的字符串入门题暴力解完、看懂题解里的 KMP 就过去了。直到后来有一次在线上排查一个日志匹配变慢的问题顺手点开了 String.indexOf 的源码才发现 JDK 底层那套字符串匹配逻辑比我印象里“就是两层循环暴力找”要讲究得多。这篇文章就把我从 LeetCode 28 出发到啃 JDK 源码、再到手动实现匹配算法这条线完整梳理一遍适合刷题时被 KMP 搞晕、或者想搞明白 Java 字符串匹配到底怎么工作的人。1. 先搞懂 LeetCode 28 到底在考什么1.1 题目本质与暴力解法的思路LeetCode 28 要求实现一个函数给定两个字符串 haystack 和 needle返回 needle 在 haystack 中第一次出现的起始下标如果不存在就返回 -1。这其实就是重新实现一遍 Java 里 String.indexOf 的核心逻辑只不过题目的输入是两个普通字符串没有对象内部的编码压缩也没有 JIT 帮你优化循环。最基本的解法是暴力匹配思路很容易理解用一个外层指针 i 遍历主串每次从 i 开始把模式串逐位和主串比较内层只要有一位不等就跳出。如果内层完整走完说明匹配成功直接返回 i主串剩余的字符数已经不足模式串长度时就可以提前结束。public int strStr(String haystack, String needle) { int n haystack.length(), m needle.length(); if (m 0) return 0; for (int i 0; i m n; i) { int j 0; while (j m haystack.charAt(i j) needle.charAt(j)) { j; } if (j m) return i; } return -1; }这段代码在 LeetCode 上能过绝大多数测试用例跑得也不慢时间复杂度最坏是 O(n*m)但平均情况远没那么糟。问题在于当主串和模式串都长得比较“刁钻”时比如 haystack 是“aaaaa...aaaaab”needle 是“aaaaab”暴力解法会反复从每个位置开始比较直到最后一个位置才匹配成功性能会退化得很难看。1.2 为什么朴素匹配在最坏场景会卡住暴力匹配慢的本质是“重复劳动”。主串指针 i 每次失配后只前进一位而内层已经比对过的信息完全没有被利用。拿上面那个例子来说第一次比对从位置 0 开始前 5 个字符都对上了第 6 个字符失败第二次又从位置 1 开始重新把这 5 个字符再比一遍。如果模式串里全是同一个字符这种重复操作的规模会随着主串长度线性放大最终变成 O(n*m)。KMP 的出发点正是解决这个重复问题失配时不让主串指针回头而是利用模式串自身的结构把模式串指针滑动到一个合理位置继续匹配。这个“合理位置”由模式串的前缀函数决定所以 KMP 能把时间复杂度压到 O(nm)。不过这里我要多说一句LeetCode 上很多题解会把 KMP 讲得玄乎实际上在日常 Java 开发里你几乎不需要自己写 KMP因为 String.indexOf 已经做了大量工程优化。搞清楚 KMP 是为了理解算法思想而不是为了在生产代码里替换 JDK 方法。这个心态摆正之后看后文会轻松很多。2. JDK 的 String.indexOf 到底是怎么写的2.1 源码逐段拆解入口到核心循环我以 OpenJDK 8 的 String 源码为例拆解因为这一版逻辑最直观JDK 9 之后的改动等会儿单独说。String.indexOf(String str) 最终会调用一个静态重载方法 indexOf(char[] source, ...)核心代码如下做了精简static int indexOf(char[] source, int sourceOffset, int sourceCount, char[] target, int targetOffset, int targetCount, int fromIndex) { if (fromIndex sourceCount) { return (targetCount 0 ? sourceCount : -1); } if (fromIndex 0) { fromIndex 0; } if (targetCount 0) { return fromIndex; } char first target[targetOffset]; int max sourceOffset (sourceCount - targetCount); for (int i sourceOffset fromIndex; i max; i) { if (source[i] ! first) { while (i max source[i] ! first); } if (i max) { int j i 1; int end j targetCount - 1; for (int k targetOffset 1; j end source[j] target[k]; j, k); if (j end) { return i - sourceOffset; } } } return -1; }很多人看这段源码第一反应是这不还是双重循环吗跟暴力匹配有啥区别区别在于细节。外层循环每移动一个位置并不是每次都老老实实从模式串第 0 位开始比而是先取出模式串的第一个字符 first在主串里快速找到 first 出现的位置只有主串当前字符等于 first 时才进入内层去逐个比较剩余字符。更妙的是那段 while 循环if (source[i] ! first) { while (i max source[i] ! first); }它的意思是如果当前位置不是 first直接继续往后扫描直到遇到 first 或者越过 max 边界。相当于把所有明显不可能匹配的位置用一次字符比较就过滤掉了。这就好比你在书里找一句话先快速扫一遍有没有某个关键标点找到一个候选位置再逐字读而不是从每个字开始都整句读一遍。2.2 边界条件处理与返回值语义源码里最容易被忽略的是开头那四个边界判断每一个都有对应语义也是 LeetCode 28 最容易漏判的地方。第一个判断如果 fromIndex 已经大于等于主串长度那么唯一可能匹配成功的情况是模式串为空字符串此时返回 sourceCount否则返回 -1。注意这里返回的是主串长度而不是 -1是因为空字符串在任何位置都能匹配JDK 把“末尾之后”也视为一种合法位置。第二个判断fromIndex 为负数时归零。这个语义和 Java 里很多 API 一致比如 Math.max(0, fromIndex)。第三个判断targetCount 0 时直接返回 fromIndex。空字符串匹配永远成功位置就是当前搜索起点。第四个判断其实不在开头而是循环里的 max 变量max sourceOffset (sourceCount - targetCount)这意味着主串剩余长度已经不足以容纳完整模式串时循环直接结束返回 -1。这是暴力匹配里“i m n”这个条件的源码版表达。这些边界看着琐碎但刷题和写代码时特别容易踩坑。LeetCode 28 的测试用例里一定会有 needle 为空串的情况返回值应该是 0也一定会有 needle 长度大于 haystack 的情况返回值应该是 -1。如果只盯着主循环写这两类用例很容易出错。2.3 JDK 9 之后的编码差异Latin1 与 UTF16JDK 9 引入了一个大改动String 内部不再用 char[] 存储而是改成 byte[] 加一个 coder 字段。coder 为 0 时表示 Latin1 编码每个字符占一个字节coder 为 1 时表示 UTF16 编码每个字符占两个字节。这个改动直接影响 indexOf 的实现。OpenJDK 里 String.indexOf(String str) 会先看看自己和参数的 coder如果两者都是 Latin1就调用 StringLatin1.indexOf否则调用 StringUTF16.indexOf。两个版本的逻辑类似但字节数组的处理方式不同Latin1 版本因为每个字符只占一字节缓存友好性更好匹配速度也更快。有一段代码值得注意StringLatin1.indexOf 里针对模式串长度为 1 和 2 的情况做了单独快速分支。长度为 1 时就是查一个字节长度为 2 时先找第一个字节再顺手确认下一个字节。这些优化说明 JDK 对于“短模式串”这种最常见的场景做了很多微调核心思想还是“首字符预筛 逐个验证”没有引入复杂的状态机。所以回到开头那个问题JDK 的 indexOf 是暴力匹配吗从算法分类角度讲它仍然是基于朴素匹配的改进不是 KMP也不是 Sunday从工程效率角度讲它通过首字符跳跃、编码压缩、短串特判等优化在真实业务场景里的表现非常好。3. 为什么 JDK 不直接用 KMP3.1 KMP 的算法优势与适用前提KMP 的高明之处在于失配时利用前缀函数把模式串滑动到合适位置主串指针永不回头时间复杂度严格 O(nm)。对于模式串“aaaaab”这种极端重复场景KMP 能给到线性时间暴力匹配则退化成 O(n*m)。但 KMP 不是没有代价。它需要额外 O(m) 的空间存前缀函数计算前缀函数也需要一次模式串的自匹配遍历。更重要的是KMP 的实现比朴素匹配复杂得多一旦写错排查的时间成本很高。LeetCode 题解里很多人会推荐 KMP是因为算法题的输入规模可以很大而且评判标准是时间复杂度的渐进上界。但 JDK 面对的场景完全不一样它不知道调用方会传多长的模式串也不知道主串和模式串的内容分布只能选一个在绝大多数情况下都表现良好、实现又足够可靠的方案。3.2 工业实现的取舍首字符预筛与 JIT 优化JDK 不直接上 KMP我个人理解有四个原因。第一真实业务里模式串通常很短。你搜索一个关键词可能就三五个字符此时 KMP 需要先 O(m) 计算前缀函数再从主串开头扫这个额外开销可能比朴素匹配节省的那点比较次数还多。JDK 的“先找首字符”策略对短模式串几乎是零成本预筛。第二JIT 编译器对简单循环的优化能力很强。一个两层 for 循环经过 JIT 编译后可能变成非常紧凑的机器码配合 CPU 的分支预测和缓存行预取跑起来比理论分析的复杂度要快得多。KMP 的主循环虽然单层但每次都要查前缀表引入了间接寻址和数据依赖反而对 CPU 流水线不友好。第三JDK 的方法要保证语义正确和线程安全不能为了最坏情况的最优复杂度牺牲可维护性。String 是 Java 里最核心的类之一indexOf 的实现必须简单、稳定、经得起所有人审查。第四KMP 的优化点在“模式串重复前缀多”时最有效比如“aaaaab”但这种输入在实际业务里出现的概率极低。JDK 团队在性能优化上向来追求“对绝大多数场景有效”而不是“对最坏场景最优”这跟算法题的思维模式完全不同。3.3 什么场景下你自己写 KMP 才有意义如果你的代码运行在一个性能敏感的环境中同一段很长的文本要被同一个模式串反复匹配那么手写 KMP 是合理的。比如你写一个数据清洗工具要从几十 MB 的日志里反复查找固定的敏感词列表此时可以提前为每个敏感词构建前缀函数然后复用或者你实现一个简单的模板引擎需要在一段大文本里查找某个标记字符串模式串固定且较长也适合 KMP。另一个有意义的方向是“多模式匹配”。如果要同时查找几百个模式串KMP 反而不够用这时候应该考虑 AC 自动机。AC 自动机可以看作 KMP 在多模式场景下的扩展把多个模式串构建成 Trie 树再补全失败指针。我们在日志关键词过滤、敏感词扫描这类场景里用的就是 AC 自动机而不是单模式 KMP。所以我的建议是LeetCode 上把 KMP 吃透理解前缀函数和主串不回退的思想工作中优先用 String.indexOf 和 String.contains只有当模式串长、复用次数多、性能数据证明瓶颈在字符串匹配时才考虑手写专用匹配逻辑。4. LeetCode 28 的高分解法从暴力到 KMP4.1 朴素实现的关键细节与易错点如果面试时时间紧写朴素解完全没问题但要保证几个细节不犯错。第一个细节是循环边界必须是 i m n写成 i n - m 也等价但很多人会多循环一次或者少循环一次。第二个细节是 needle 为空串要返回 0这是题目的明确约定。第三个细节是内层比较用 while 循环时退出后要判断 j m 再返回 i不能一退出就返回。我自己刷题时还犯过一个错在主指针 i 移动时如果内层匹配到一半失败直接把 i 加 1但忘记把 j 重置为 0。写成 for 循环且在外层初始化 j 0 的话这个错很容易避免但用 while 循环写就要特别小心。这段朴素代码的时间复杂度平均能过题但如果你担心极端用例可以加一个快速判断如果 m n直接返回 -1如果 m 0直接返回 0。这两个判断能省掉很多无意义的循环。4.2 前缀函数与 KMP 手写要点KMP 的实现我推荐用“前缀函数”版本不要背教材里那种 next 数组从 -1 开始的写法。前缀函数的定义是pi[i] 表示模式串中以下标 i 结尾的子串里最长的相等真前后缀长度。计算它用的是一段非常优雅的自匹配代码public int[] prefixFunction(String pattern) { int m pattern.length(); int[] pi new int[m]; for (int i 1; i m; i) { int j pi[i - 1]; while (j 0 pattern.charAt(i) ! pattern.charAt(j)) { j pi[j - 1]; } if (pattern.charAt(i) pattern.charAt(j)) { j; } pi[i] j; } return pi; }这里有个理解难点为什么失配时 j 要跳到 pi[j - 1]因为 j 代表的是“已经匹配上的前缀长度”现在这个前缀的下一个字符失配了我们需要在这个前缀里找它的最长相等前后缀这正是 pi[j - 1] 的含义。画一画“ababc”的前缀函数就能看明白pi [0, 0, 1, 2, 0]中间那个 2 表示子串“abab”的最长相等前后缀是“ab”长度为 2。匹配阶段的主循环更简单主串指针永远不回头public int strStr(String haystack, String needle) { int n haystack.length(), m needle.length(); if (m 0) return 0; int[] pi prefixFunction(needle); int j 0; for (int i 0; i n; i) { while (j 0 haystack.charAt(i) ! needle.charAt(j)) { j pi[j - 1]; } if (haystack.charAt(i) needle.charAt(j)) { j; } if (j m) { return i - m 1; } } return -1; }写的时候注意一点当 j m 说明完整匹配成功返回的起始下标是 i - m 1因为此时 i 指向模式串最后一个匹配字符的下标。这个偏移很多人会算错。4.3 提交答案时实测性能对比与选型建议我在 LeetCode 上分别提交过朴素解和 KMP 解针对官方测试集两者都能通过但耗时和内存有明显差异。朴素的平均耗时大约在 3-4ms 左右KMP 大约 1-2ms。如果测试用例里有超长重复模式串朴素解的耗时可能会飙到几十毫秒KMP 稳定在线性时间。但这里要说句公道话算法题里的字符串长度通常也就几千到几万KMP 和朴素解在真实用户体验上的差距很小。KMP 的真正价值是在理论复杂度上有保障以及它背后“空间换时间、利用已匹配信息”的思想是很多进阶算法的地基。如果面试官问你“还能不能再优化”除了 KMP你还可以提 BM 算法和 Sunday 算法。Sunday 算法在工程上实现简单、平均表现好核心思想是匹配失败时看主串中模式串后一位字符用它决定跳多远。了解这些算法的存在和优劣比背熟每一种的模板更有用。5. 实战中 String 匹配的常见坑与排查实录5.1 indexOf 返回值最容易踩的三个坑第一个坑是把返回值当成布尔判断。indexOf 找到时返回下标找不到时返回 -1但找到的位置完全有可能是 0所以绝不能写 if (str.indexOf(xxx))否则字符串开头匹配时判断永远为“假”。正确写法是 if (str.indexOf(xxx) 0) 或者直接用 contains。第二个坑是忽略空字符串的情形。str.indexOf() 返回 0str.contains() 返回 true。有些新手拿 indexOf 判空结果永远匹配成功。需要判空请用 str.isEmpty() 或 str.length() 0。第三个坑是 fromIndex 的语义。indexOf(String str, int fromIndex) 里的 fromIndex 是“从这个下标开始向后搜索”包含这个下标本身。如果你想要的是“从某个位置之后第一次出现”就要传 fromIndex 1。这个细节在解析字符串、切分日志时经常踩我见过有人用 indexOf 循环找所有匹配位置因为忘记加 1 导致死循环CPU 直接打满。正确的循环写法是每次把上次找到的位置加 1 再传进去直到返回 -1。5.2 字符串匹配性能排查的几个方向线上如果发现字符串操作成为热点先不要急着换算法按下面几层排查。第一层是看数据规模和数据分布。主串有多长模式串有多长是否大量重复如果主串几千字节、频率不高直接忽略优化瓶颈大概率在别处。第二层是看是否每次都在重新搜索同一个模式串。如果一段文本要反复查同一个关键词考虑把关键词对应的匹配结果缓存或者把文本预处理成更适合检索的结构比如构建索引。第三层是看字符编码。JDK 9 之后字符串如果是纯 ASCII 或 Latin1 范围内容内部走单字节快速路径如果混入了中文等超出 Latin1 范围的字符String 会使用 UTF16 编码同样长度的字符串在匹配时的内存带宽消耗会翻倍。在做海量短文本匹配时尽量统一字符范围或者在存储层就做好编码规划对性能影响很明显。第四层是看是否频繁创建子串。substring 在 JDK 7 之前会共享底层 char[]JDK 7 之后改成复制频繁 substring 会产生大量新对象建议用 indexOf regionMatches 代替或者用 CharSequence 视图避免复制。5.3 从 LeetCode 28 延伸出去contains / regionMatches / startsWith 的关系String.contains 的实现就是 return indexOf(s) 0所以 contains 不会比 indexOf 慢。String.startsWith 在 JDK 里的实现是调用 regionMatches 的简化版它不从头部找任意位置而是只检查指定偏移位置开始是否与目标串相等复杂度 O(m)没有预筛逻辑。String.endsWith 同理本质也是 regionMatches。这些方法之间的关系可以帮你写出更清晰的业务代码。比如要判断“字符串里是否存在指定关键词”用 contains要判断“从第几个字符开始是不是某个串”用 regionMatches要判断“是否以某前缀开头”用 startsWith。它们底层逻辑各不相同但都建立在字符串数组的逐字节比较之上理解了 indexOf 这一层再去看这些方法会容易得多。6. 从刷题到读源码一条可以复制的学习路径我整理一下自己这次研究的路径大家可以照着走一遍先在 LeetCode 上把 28 题的暴力解写对然后把 KMP 的前缀函数和匹配主循环抄一遍、自己推导几组例子再去 OpenJDK 源码里搜 String.indexOf把 char[] 版、byte[] 版、Latin1 版分别看一遍最后用 Java Microbenchmark HarnessJMH写个小基准测一测 indexOf 在不同模式串长度下的表现。这个过程最关键的收获不是“学会了 KMP”而是建立起“算法题解法”和“工业级实现”之间的对照意识。算法题里的暴力解、最优解对应的是理论上的复杂度上下界JDK 源码里那些看似朴素的循环其实是在大量真实数据分布、CPU 架构、JIT 行为约束下做出的工程折中。理解了这层折中你读任何底层库的源码都不会再问“为什么不用更高级的算法”。我实测的一个有意思结论是模式串固定重复匹配几千次时KMP 比 JDK indexOf 快大约 20%-30%但代码复杂度和维护成本高出一大截。如果模式串只有一二十个字符JDK indexOf 的首字符预筛配合 JIT经常能跟 KMP 打平甚至反超。这就是为什么我说“不要盲目替换库函数”。最后分享一个实用小技巧如果你在源码里看到 indexOf 内部的 while 循环看不懂可以把整个方法复制出来加上打印语句再用一个短例子跑一遍。比如主串“mississippi”、模式串“issip”单步跟踪 i、j、max、end 这几个变量的变化比盯着静态代码理解快得多。源码这东西读一遍不如跑一遍跑一遍不如改着玩一遍。