做 LeetCode 刷题复盘最忌讳的就是看了一遍题解觉得自己懂了关掉页面下次照样写不出来。第 28 题《找出字符串中第一个匹配项的下标》就是典型——题目一句话能说清给定主串 haystack 和模式串 needle返回 needle 在 haystack 中第一次出现的下标找不到就返回 -1。老版本题目还叫实现 strStr()直接对应 C 语言标准库里的同名函数。看起来简单可真要你从暴力解一路讲到 KMP再聊到滚动哈希、BM 算法很多人就撑不住了。这篇文章把我自己刷这道题的完整过程、边界条件踩坑记录、KMP 的前缀表原理推导以及在面试场景里怎么把这道题讲出层次感的经验全部拆开揉碎了放出来适合所有刚开始刷题、或者刷过但没真正吃透字符串匹配的朋友。1. 先看清题目它到底在考什么1.1 原题还原与容易忽略的边界题目输入是两个字符串haystack 和 needle。haystack 翻译过来是草堆needle 是针英文里这个命名非常形象——大海捞针。你需要返回 needle 在 haystack 中第一次出现的起始下标如果它压根不存在返回 -1。举个例子就明白haystack sadbutsadneedle sad返回 0因为下标 0 处就是第一个 sad另一个例子 haystack leetcodeneedle leeto返回 -1因为 leeto 根本不存在。很多人一上来就写暴力循环结果提交发现边界直接挂掉十有八九是没处理 needle 为空或者模式串长度大于主串的情况。这里要记住两个约定按 strStr() 的语义当 needle 为空字符串时应该返回 0因为空串可以认为在任意位置匹配标准实现一般取起点 0而当 haystack 为空但 needle 非空或者 n m 时haystack 里不可能装下 needle直接返回 -1。我建议在写任何解法之前先把这几条边界列到注释里m 0返回 0n 0 或 n m返回 -1完全相等返回 0完全没有匹配返回 -1不要觉得这些是废话。暴力解法外层循环的边界、KMP 匹配时针的移动、滚动哈希的窗口滑动每一处都依赖你对这些边界的正确判断。把边界想清楚再动手比写完了反复调试省时间得多。1.2 为什么字符串匹配值得专门刷一遍字符串匹配不是只在 LeetCode 上存在的抽象问题。你在文本编辑器里按 CtrlF 查找关键词在日志系统里过滤报错信息在爬虫解析 HTML 时定位某个标签底层都涉及子串搜索。整个算法领域里有大量经典匹配方案从最朴素的暴力扫描到 KMP、Boyer-Moore、Sunday、Rabin-Karp再到工程界常用的各种混合变体每一个都有它自己的适用场景和取舍逻辑。第 28 题恰好是这个领域最好的入门入口。它的门槛很低——暴力解三分钟能写完在比较宽松的测试数据下也能通过但它的上限很高面试官完全可以从这道题顺藤摸瓜先让你写暴力再问你能不能优化接着问 KMP 的 next 数组怎么求再问 为什么 KMP 是 O(nm)一层比一层深。很多人题解看过就忘本质原因是只记住了代码模板没搞懂每个关键步骤背后的为什么。这篇文章我会把每一个关键选择背后的逻辑都讲透你照着思路走一遍下次再遇到字符串匹配的变体题就不会只有模糊印象了。2. 暴力匹配先把功能跑通再说优化2.1 暴力解法实现与逐行说明暴力匹配的思路没有任何花哨从 haystack 的每一个可能起点出发把 needle 的字符一个一个比过去如果中间某个字符对不上就放弃当前起点挪到下一个位置重新比。Python 实现大概是这样的class Solution: def strStr(self, haystack: str, needle: str) - int: n, m len(haystack), len(needle) if m 0: return 0 if n m: return -1 for i in range(n - m 1): j 0 while j m and haystack[i j] needle[j]: j 1 if j m: return i return -1这里第一个要注意的点是外层循环只走到n - m 1而不是n。为什么因为从下标 i 开始往后至少要剩余 m 个字符才可能完整容纳一个 needle。如果写成range(n)当 i 太大时访问haystack[i j]就会越界。这是暴力解法最常见的错误之一尤其在 Python 里越界不会像 C 语言那样直接崩溃有些时候会返回错误结果排查起来更费劲。其实还有一个更 Pythonic 的写法直接用切片比较class Solution: def strStr(self, haystack: str, needle: str) - int: n, m len(haystack), len(needle) for i in range(n - m 1): if haystack[i:i m] needle: return i return -1两行核心逻辑非常好读。这里range(n - m 1)在 n m 时自动退化成空范围循环不执行直接返回 -1所以表面上可以省略 n m 的判断。不过我个人还是习惯把m 0和n m的边界显式写出来一方面语义清晰另一方面也提醒自己不要漏掉特殊情况。肯定有朋友想问Python 不是有现成的find()方法吗return haystack.find(needle)一行不就完了话是没错但刷题的目的是理解匹配原理而不是调标准库接口。CPython 里str.find的底层实现相当讲究用的是经过优化的两阶段匹配策略速度远快于手写的暴力版本但那属于解释器层面的工程优化和这道题考察的数据结构与算法是两码事。面试时你要是这么回答大概率会被认为在回避问题。2.2 复杂度分析暴力慢不是没道理的暴力匹配的时间复杂度是 O(nm)。n 是主串长度m 是模式串长度。最好情况是 O(n)比如主串是aaaaaaaaaaaaab模式串是ab那么每个起点比较到第一个字符时就能发现不匹配很快跳过最坏情况是 O(nm)比如主串是aaaaaaaaaaaaab模式串是aaaab每个起点都要一路比较到最后一个字符才发现问题然后 i 只往后挪一位把所有前缀匹配信息全部丢掉重头再比一遍。LeetCode 这道题的数据范围我记得两个字符串长度上限大概在 10^4 的量级。也就是说最坏情况下 O(n*m) 会达到 10^8 次字符比较Python 在这种量级下很容易超时。很多题解说暴力也能过那是没碰到最极端的测试用例或者运气好逃过了性能测试。稳妥起见下一节讲的 KMP 才是一劳永逸的正解。但暴力解完全不是毫无价值。它的空间复杂度是 O(1)代码极短可读性最好用来在面试初期保底、梳理思路非常合适。关键是你要能在面试官追问能不能优化的时候立刻接上 KMP。如果交了一版暴力之后愣住那这道题在面试里基本算半放弃了。3. KMP 算法字符串匹配的经典正解3.1 暴力到底浪费了什么信息要理解 KMP先要看清楚暴力算法把信息浪费在了哪里。用这个例子来说明haystack aabaabaafneedle aabaaf。暴力匹配从下标 0 开始比到下标 5 时发现主串当前字符是b而模式串下标 5 的字符是f不匹配。接下来暴力做了什么把起点挪到 1拿主串下标 1 的a重新和模式串开头的a比然后再挪到 2拿b重新比一直到起点 3才真正匹配上。问题在于在下标 5 失败的那一刻我们已经知道了主串 0 到 4 的字符是aabaa也知道了模式串 0 到 4 的字符同样是aabaa。这些信息完全足够推理出主串从下标 1 或 2 开头是不可能匹配成功的因为它们开头的后缀结构和模式串的前缀结构对不上。可是暴力算法不利用这些信息只是在原地打转一遍又一遍重新比较。KMP 的核心思想用一句话概括匹配失败时主串指针 i 不回退只回退模式串指针 j而且回退到哪个位置由模式串自身的结构提前算好。这个提前算好的结构就是前缀表也就是大家常说的 next 数组。3.2 前缀表KMP 的核心概念什么叫最长相等前后缀一个字符串的前缀是去掉最后一个字符后剩下的头部子串后缀是去掉第一个字符后剩下的尾部子串。某个前缀子串的最长相等前后缀就是在这个子串内部头部和尾部相同的那一段最长部分的长度。用 needle aabaaf手算一遍前缀a单个字符没有真前后缀最长相等前后缀长度 0next[0] 0前缀aa前缀a等于后缀a长度 1next[1] 1前缀aab前缀有a、aa后缀有b、ab没有相等的next[2] 0前缀aaba前缀a等于后缀a长度 1next[3] 1前缀aabaa前缀aa等于后缀aa长度 2next[4] 2前缀aabaaf没有相等前后缀next[5] 0所以 next [0, 1, 0, 1, 2, 0]。next 数组在匹配时怎么用当主串与模式串在模式串下标 j 处失配j 回退到 next[j-1]而不是 next[j]。原因在于失配发生在 j说明模式串 0 到 j-1 已经全部匹配成功我们现在要利用的是已匹配部分本身的相等前后缀结构。继续用刚才的例子匹配到 j 5 时失配主串 0 到 4 这一段是aabaa它的最长相等前后缀是aa长度 2。这个信息说明主串当前失败位置之前末尾的两个aa已经和模式串开头的aa对上了所以完全不用把主串指针退回去也不需要从模式串的 0 重来直接把 j 回退到 2拿主串当前的b和模式串下标 2 的b继续比较就好了。这一步回退直接省掉了暴力算法里从下标 1、2 出发的两次完整尝试。3.3 next 数组的完整实现求 next 数组的过程本质上就是模式串自己和自己匹配。用两个指针i 遍历模式串表示现在要计算 next[i]j 表示已经匹配的前后缀长度同时也是下一轮要比较的模式串下标。模板代码写出来是这样的def build_next(pattern: str) - list: m len(pattern) nxt [0] * m j 0 for i in range(1, m): while j 0 and pattern[i] ! pattern[j]: j nxt[j - 1] if pattern[i] pattern[j]: j 1 nxt[i] j return nxt逐个拆解一下nxt[0] 恒为 0因为单个字符没有真前后缀。i 从 1 开始每次尝试把新字符 pattern[i] 接到已经匹配的前后缀后面。如果 pattern[i] 和 pattern[j] 相等说明最长相等前后缀长度可以加 1于是 j 1赋给 nxt[i]。如果不相等j 不能直接归零而是回退到 nxt[j-1]继续尝试更短的相等前后缀。这里的回退逻辑和后面真正匹配时的回退逻辑完全一致。很多人卡在失配后回退到 nxt[j-1] 而不是 nxt[j]这个点上想不通。核心原因很简单nxt[j-1] 表示的是已经匹配成功的前缀 pattern[0:j] 内部最长相等前后缀的长度。当 pattern[j] 失配时说明我们原来期望的能匹配长度为 j 的前缀这条路走不通了但我们不想完全放弃而是退而求其次在这个已经匹配的前缀里找一个更短的、仍然可能继续匹配的前缀长度。这个更短的长度正是 nxt[j-1]。用 pattern aabaaf走一遍 next 构建i 1pattern[1] aj 0相等j 1nxt[1] 1i 2pattern[2] bj 1pattern[1] a 不相等回退 j nxt[0] 0比较 pattern[0] a仍不相等nxt[2] 0i 3pattern[3] aj 0相等j 1nxt[3] 1i 4pattern[4] aj 1相等j 2nxt[4] 2i 5pattern[5] fj 2pattern[2] b 不相等回退 j nxt[1] 1pattern[1] a 不相等回退 j nxt[0] 0pattern[0] a 不相等nxt[5] 0最终得到 [0, 1, 0, 1, 2, 0]和手算结果完全一致。你可以在纸上多找几个模式串自己推一遍这一步真正搞懂了KMP 就掌握了八成。3.4 用 next 数组完成一次不回头的匹配有了 next 数组KMP 的匹配过程极其简洁。主串指针 i 永远只前进模式串指针 j 根据 next 数组回退class Solution: def strStr(self, haystack: str, needle: str) - int: n, m len(haystack), len(needle) if m 0: return 0 if n m: return -1 nxt build_next(needle) j 0 for i in range(n): while j 0 and haystack[i] ! needle[j]: j nxt[j - 1] if haystack[i] needle[j]: j 1 if j m: return i - m 1 return -1逐行解读匹配过程外层 for 循环遍历主串每个字符i 从不回退。内层 while 在失配时把 j 回退到 next 数组指定的位置直到 j 变成 0 或者当前字符匹配成功。如果匹配成功j 加 1。一旦 j 达到 m说明模式串完整匹配此时起点下标是 i - m 1。还是用aabaabaaf和aabaaf完整走一遍i 0主串 a 与模式串下标 0 的 a 相等j 1i 1主串 a 与模式串下标 1 的 a 相等j 2i 2主串 b 与模式串下标 2 的 b 相等j 3i 3主串 a 与模式串下标 3 的 a 相等j 4i 4主串 a 与模式串下标 4 的 a 相等j 5i 5主串 b 与模式串下标 5 的 f 失配j 回退到 nxt[4] 2发现主串 b 与模式串下标 2 的 b 相等j 3i 6主串 a 与模式串下标 3 的 a 相等j 4i 7主串 a 与模式串下标 4 的 a 相等j 5i 8主串 f 与模式串下标 5 的 f 相等j 6等于 m返回 8 - 6 1 3整个过程主串只遍历了一遍。构建 next 数组是 O(m)匹配是 O(n)总时间复杂度 O(nm)。空间复杂度 O(m)用来存 next 数组。KMP 是线性算法的原因就在这主串指针 i 从不后退模式串指针 j 虽然会回退但 j 整体上的移动量是被主串比较次数约束住的不会出现 O(n*m) 级别的重复比较。4. 刷这道题最容易踩的坑4.1 边界条件速查表写这道题最容易翻车的地方全在边界条件上。我把它们整理成一个速查表场景期望结果说明needle 为空0空串匹配任意主串起点取 0haystack 为空needle 非空-1主串里不可能找到模式串n m-1模式串比主串还长不可能匹配haystack 与 needle 完全相等0整体就是一次匹配首尾都有匹配返回最早的下标题目要求第一次出现的位置needle 是 haystack 的子串但不在开头返回实际下标比如 hello 找 ll 返回 2还有一个我在面试里经常提醒自己的点写完代码先不要急着提交手动跑一遍这些用例。如果你用 Python 的切片版本n m 的情况会被空 range 自然处理掉如果你用双指针暴力版本就必须显式判断。无论如何m 0 这个分支一定不能省这是 strStr() 语义的一部分也是很多测试用例会覆盖的隐藏点。4.2 next 数组相关的高频错误KMP 的坑主要集中在 next 数组上。我见过太多人写 KMP 时栽在下面这几个地方第一nxt[0] 初始化为 1。这是对最长相等前后缀理解不到位造成的。单个字符没有真前后缀nxt[0] 必须为 0。如果这里错成 1后面整个数组都会偏一位匹配时 j 回退的位置全部不对。第二回退下标写错。失配时应该执行j nxt[j - 1]很多人手滑写成j nxt[j]。差一个下标结果完全不一样。记住一个判断技巧失配发生在 j说明 0 到 j-1 这段是匹配上的我们能利用的信息只存在于已经匹配的这段里所以一定取 nxt[j-1]。第三返回下标算错。匹配成功时j m 发生在主串下标 i 处起点应该是i - m 1。有人会写成i - m有人会写成i。你只要想清楚j 表示已经匹配了多少个字符最后一个匹配字符落在主串下标 i 上那么匹配区间就是[i - m 1, i]起点自然是i - m 1。第四构建 next 和匹配过程混淆。构建 next 时比较的是pattern[i]与pattern[j]匹配时比较的是haystack[i]与needle[j]两段代码看起来很像但对象完全不同。我见过有人直接把构建 next 的循环抄到匹配里结果拿模式串自己和主串比跑出了完全错误的结果。写的时候最好分成两个函数命名区分清楚。4.3 实测暴力在什么时候会翻车我在本地做过一次简单测试用全a的主串和模式串构造最坏情况比如主串长度 10^4模式串长度 5000 且最后一位是b。暴力解法在这种输入下需要执行的字符比较次数接近 5x10^7 量级Python 实测耗时大约在秒级甚至更高提交到评测系统里很容易被卡时间。同样的数据 KMP 几乎是瞬间完成因为主串只扫描一遍字符比较次数和 nm 同阶。但也不是说暴力一无是处。如果模式串很短比如 m 只有 10 以内或者主串和模式串都是随机文本失配通常发生在很靠前的位置暴力的实际性能往往还不错因为期望比较次数接近 n而不是 n*m。这就是为什么在工程里很多简单的字符串查找实现反而直接用暴力加一点剪枝比如先用首字符快速定位候选点。可到了算法面试里你没法保证测试数据是随机善良的所以 KMP 这种在任意输入下都稳定的线性算法才值得花时间吃透。另外提一句 Python 性能细节切片比较haystack[i:im] needle虽然代码简洁但每次切片都会创建新的字符串对象内存和时间开销都不小。在极端数据下切片版本的暴力可能比双指针版本更慢。刷题时为了稳妥我倾向于用双指针版本除非题目明确限制了数据规模很小。5. 想跟面试官多聊两句还有这些匹配思路5.1 滚动哈希Rabin-Karp 的思路如果面试官在 KMP 之后继续追问还有没有别的办法滚动哈希是一个很好的谈资。它的思路是把每个子串都映射成一个哈希值先比较哈希值哈希相等再去真正比较字符串从而把单次子串比较的时间降到 O(1) 平均。class Solution: def strStr(self, haystack: str, needle: str) - int: n, m len(haystack), len(needle) if m 0: return 0 if n m: return -1 base 26 mod 10**9 7 needle_hash 0 window_hash 0 for i in range(m): needle_hash (needle_hash * base (ord(needle[i]) - 97)) % mod window_hash (window_hash * base (ord(haystack[i]) - 97)) % mod if needle_hash window_hash and haystack[:m] needle: return 0 power 1 for _ in range(m - 1): power (power * base) % mod for i in range(1, n - m 1): window_hash (window_hash - (ord(haystack[i - 1]) - 97) * power) % mod window_hash (window_hash * base (ord(haystack[i m - 1]) - 97)) % mod if needle_hash window_hash and haystack[i:i m] needle: return i return -1核心代码是窗口哈希的滚动更新每向右滑动一个字符先减去左端字符的贡献再整体乘以进制数 base然后加上右端新字符的贡献。这样才能在 O(1) 时间内从旧窗口哈希推到新窗口哈希。这里power是base^(m-1) mod mod表示最左边字符在窗口里所带的权重。有一个细节必须注意哈希值相等不代表字符串一定相等可能存在哈希碰撞。所以我在代码里每次哈希相等后都附加了一层真正的字符串比较haystack[i:im] needle。这个双重检查让算法在碰撞时能正确跳过误报。Rabin-Karp 的平均时间复杂度是 O(nm)但如果碰撞设计得很糟糕最坏情况会退化到 O(n*m)。不过在实际刷题和工程场景里取一个合理的大质数作为模数碰撞概率非常低性能表现很稳定。5.2 算法横向对比把几种匹配方案放在一张表里对比能帮助你快速判断不同场景该选谁算法时间复杂度空间复杂度特点与适用场景暴力O(n*m)O(1)简单直接模式串短时可用KMPO(nm)O(m)稳定线性适合模式串有重复前缀的情况Rabin-Karp平均 O(nm)最坏 O(n*m)O(1)适合多模式串批量匹配比如查重Boyer-Moore / Sunday平均亚线性O(m)工程中常用适合大文本搜索实际工程里很多字符串查找库并不会单独用 KMP而是用 BM 或 Sunday 这类从右往左比较的算法因为它们在随机文本上的平均性能往往比 KMP 更好。但 KMP 在算法题里地位独特因为它用最简单的方式把动态规划思想应用在字符串匹配这件事情讲清楚了这也是面试官偏爱它的原因。5.3 面试答题的节奏建议如果你在面试中遇到这道题我的建议是不要一上来就闷头写 KMP。先把暴力解写出来并说明复杂度主动提出边界条件让面试官看到你的思维是完整的。等面试官追问能不能优化你再引出 KMP重点讲三件事第一暴力浪费了已匹配信息第二前缀表如何用模式串自身结构避免重复比较第三为什么 KMP 是线性的。这样一层一层展开比自己不说话直接甩出最终代码要加分得多。如果面试官继续深挖可以聊 Rabin-Karp 的哈希思路、BM 的坏字符规则、Sunday 的偏移表。这些内容哪怕只是提个名字也能体现你的知识面。但注意控制节奏KMP 的原理和代码必须是最熟的这块才是核心竞争力。我个人在刷这道题时最大的体会是KMP 的代码模板其实很短但真正把它变成自己的东西需要亲手推演至少三遍——第一遍推 next 数组的构建第二遍推匹配过程第三遍找一个比较刁钻的模式串比如ababaca完整模拟一遍。纸上得来终觉浅字符串匹配这类题尤其如此。如果你能不看模板从零推导出 next 数组构建代码那这道题才算真正吃透了。以后再遇到任何字符串查找的变体题比如 LeetCode 的重复子字符串问题、通配符匹配问题你都会有抓手因为它们本质上都在考同一个东西如何高效地利用已经拿到的匹配信息。