企业官网建设流程全解析

1. 每日算法题 11：一道字符串匹配题背后的 KMP 原理

先说一下这个系列的背景。每天安排一道算法题，不是为了刷数量，而是把零散的知识点串成体系。第 11 期我选了字符串匹配这个方向，因为字符串相关的问题在实际业务里出现频率非常高——从日志检索、关键词过滤到基因序列比对，本质都是在做模式串匹配。今天的题目是：给定文本串 T 和模式串 P，找出 P 在 T 中首次出现的位置；如果不存在则返回 -1。

很多朋友第一反应是暴力匹配：从 T 的每个位置开始，逐个字符和 P 比较，失败就后移一位。这个思路没有错，但最坏情况下的时间复杂度是 O(n*m)，当文本串是几百万字符、模式串又长又有大量重复前缀时，性能完全扛不住。所以这题的核心考点就是 KMP 算法，它能把匹配过程优化到 O(n+m)，线性时间复杂度，这也是面试里极其高频的算法知识点。本期我就围绕这道题，把 KMP 的前因后果、next 数组的推导、代码实现和容易踩的坑一次讲透。

2. 暴力匹配为什么不行：先看清问题本质

2.1 一次失败的匹配里有多少信息被浪费了

假设文本串 T = "abacababacab"，模式串 P = "abacaba"。暴力匹配的做法是从 T[0] 开始逐位比较 P[0..6]，比较到 T[6] 时发现字符不匹配，于是把模式串整体右移一位，再从 P[0] 重新开始比较。这样做的问题在于，前一轮已经匹配成功的 6 个字符信息，在右移一位之后完全被丢弃了，下一轮又从零开始比较。

举个更直观的例子。模式串 P = "abacaba"，前面 6 个字符 "abacab" 已经匹配上了，第 7 个字符失配。此时其实可以观察到，"abacab" 有着明显的前后缀重复结构——前缀 "ab" 和后缀 "ab" 是相同的。这意味着模式串右移时不必只移动一位，而是可以直接跳到让前缀和后缀对齐的位置，省掉中间大量无效的比较。暴力匹配浪费的正是这部分可预判的信息。

2.2 KMP 的核心思想：让模式串自己记住该跳到哪

KMP 算法做了一个很朴素但很聪明的改变：在匹配之前，先对模式串做一次预处理，算出一个 next 数组。next[i] 的含义是：当 P[i] 失配时，i 应该回退到哪个位置继续比较。这里的回退依据是 P[0..i-1] 中最长的相等前后缀长度。

这样在匹配过程中，文本串的指针永远不需要回退，只有模式串的指针在失配时按 next 数组跳转。整体复杂度从暴力法的 O(n*m) 降到了 O(n+m)，因为每个字符最多被比较两次——一次匹配成功，一次失配跳转。理解这个思想，比记住代码重要得多，因为凡是涉及到"重复前缀匹配"的场景，这个思路都能复用。

3. 动手推导 next 数组：以 P = "abacaba" 为例

3.1 前缀和后缀的定义要抠清楚

在计算 next 数组之前，必须先明确什么是字符串的前缀和后缀。一个字符串的前缀是去掉最后一个字符后剩下的任意头部子串，后缀是去掉第一个字符后剩下的任意尾部子串。以 "abacab" 为例，它的前缀集合包括 "a"、"ab"、"aba"、"abac"、"abaca"，后缀集合包括 "b"、"ab"、"cab"、"acab"、"bacab"。这里 "ab" 既是前缀也是后缀，长度为 2。所谓最长相等前后缀，就是取所有既是前缀又是后缀的子串里最长的那一个的长度。

这里有一个新手特别容易懵的地方。计算 next[i] 时，考察的是 P[0..i-1] 这个子串的相等前后缀，而不是 P[0..i]。比如 next[6]，要看的是 P[0..5] = "abacab" 的最长相等前后缀，结果是 "ab"，长度 2，所以 next[6] = 2。这个"少看一位"的定义，是为了让 next[i] 能直接作为失配后的回退位置——因为第 i 位失配时，前面 0 到 i-1 位都已经匹配成功了。

3.2 逐位推导：从 next[0] 到 next[6]

下面我完整推导一遍 P = "abacaba" 的 next 数组，手把手带大家走一遍这个过程。next[0] 没有前面的子串，惯例上设为 -1，表示模式串已经退无可退，此时文本串指针需要前进一位。next[1] 考察的是 P[0] = "a" 的相等前后缀，前缀集合为空，后缀集合也为空（前面说了要去掉首尾字符），所以相等前后缀长度是 0，next[1] = 0，意味着失配后从头开始比较。

接下来是核心推导过程，我一个位置一个位置来：

这里有一个手动推导的小技巧。计算 next[i] 时不需要真的把前缀后缀集合全部列出来，只需要从头尾同时往中间比对，看最多能匹配多长。比如算 next[6]，看 "abacab"，首字母 a 和尾字母 b 不相等，那最长相等前后缀长度不可能超过 1？不对，这里要注意，最长相等前后缀不一定要求首尾字符相等。正确的检查方式是先看长度为 1 的前后缀 "a" 和 "b"，不等；再看长度为 2 的前后缀 "ab" 和 "ab"，相等，所以结果是 2。再看长度为 3 的前后缀 "aba" 和 "cab"，不相等。所以最长就是 2。

实际手算的时候，从长度 1 开始逐层增加也很容易出错，我更推荐的做法是：从可能的最大长度开始递减检查。最大长度是 i-1，对于 "abacab"，最大是 5，但显然前后缀差异很大，很快就能排除，落到 2 上。熟练之后，一眼扫过去就能找到对称的重复片段。

4. 代码落地：KMP 匹配的完整实现与细节打磨

4.1 预处理 next 数组的代码怎么写

理解了手动推导，接下来就是把思路翻译成代码。计算 next 数组的过程本质上也是一个"自我匹配"的过程，它的巧妙之处在于用两个指针 i 和 j，j 表示当前已匹配的前缀长度，i 表示正在计算的 next 数组下标。直接看代码：

def build_next(p): m = len(p) nxt = [-1] * m i, j = 0, -1 while i < m - 1: if j == -1 or p[i] == p[j]: i += 1 j += 1 nxt[i] = j else: j = nxt[j] return nxt

这段代码的退出条件是 i 到达 m-1，因为 next 数组只需要计算到最后一个下标。我初次看这段代码时也觉得很绕，这里拆解一下。j 初始化为 -1，表示当前没有匹配的前缀。当 p[i] 和 p[j] 相等时，说明匹配长度可以加 1，所以 i 和 j 同时自增，nxt[i] 就记录下了这个长度。当不相等时，j 回退到 nxt[j]，这个操作和匹配阶段失配时的回退逻辑完全一致。把 next 数组的计算理解成"模式串和自己做匹配"，很多疑问就通了。

4.2 匹配阶段实现：文本串指针不回退，模式串指针灵活跳转

预处理完成之后，匹配阶段的代码非常简洁：

def kmp_search(text, pattern): n, m = len(text), len(pattern) if m == 0: return 0 nxt = build_next(pattern) i, j = 0, 0 while i < n: if j == -1 or text[i] == pattern[j]: i += 1 j += 1 else: j = nxt[j] if j == m: return i - m return -1

这里有几个关键点需要特别说明。第一，当 j == -1 时，说明模式串已经回退到了无法再回退的位置，此时文本串指针必须向前移动一位，模式串指针归零，相当于从这一位重新开始匹配。第二，当 j 增加到 m 时，说明模式串已经完全匹配成功，此时文本串指针 i 指向的是匹配末尾的后一位，所以起始位置是 i - m。第三，如果文本串遍历完还没有返回，说明不存在匹配的子串，返回 -1。

4.3 一个具体的模拟过程：把代码跑在例子上

理论说得再多，不如亲手模拟一遍。用 T = "abacababacab"，P = "abacaba"，我把匹配过程中关键的指针变化列出来：

初始状态 i=0，j=0，开始逐位比较。T[0..5] 和 P[0..5] 完全匹配，i=6，j=6。此时比较 T[6] 和 P[6]，T[6] 是 'b'，P[6] 是 'a'，失配。按照 next 数组，j 回退到 nxt[6] = 2。注意这里文本串的 i 没有动，还是 6。

接着从 P[2] 开始继续比较，P[2] 是 'a'，T[6] 是 'b'，又失配。j 回退到 nxt[2] = 0。P[0] 是 'a'，T[6] 是 'b'，还是失配。j 回退到 nxt[0] = -1。此时 j == -1，i 前进到 7，j 归 0。从 T[7] 开始重新匹配，T[7..13] 恰好与 P[0..6] 完全一致，匹配成功，返回起始位置 7。

这个模拟过程很好地体现了 KMP 的优势：i 从 0 到 13 单调递增，全程没有回退，失配时模式串指针最多跳回几次就能继续前进。对比暴力法，在 i=6 处失配后要尝试 i=1、2、3 等位置，每轮都要重新比较前几个字符，额外开销是很大的。

5. 常见问题与避坑记录：这些坑我基本都踩过

5.1 next 数组定义不统一导致的混淆

关于 next 数组，网上有两种常见定义。一种是本文使用的"失配后回退的位置"，即 next[0] = -1；另一种是"最长相等前后缀长度"，最前面的可以设为 0，匹配时失配后拿 next[j-1] 来跳转。这两种定义写出来的代码不一样，但核心原理完全相同。新手最容易被这个搞晕，看一篇博客是一个写法，换一篇又不一样，很容易自我怀疑。

我的建议是：选定一种定义，把它的代码写熟、把模拟过程手推一遍，形成肌肉记忆。面试时如果面试官问到了，先明确自己用的是哪种定义，再写出对应的代码，这就不会出问题。不要试图同时记忆两种写法，容易串。

5.2 build_next 里 i 和 j 的边界条件

写 build_next 时最容易出错的是循环边界。如果 while 条件写成 i < m，那么当 i 到达 m-1 时可能还会继续访问 nxt[i+1]，造成数组越界。标准的写法是 while i < m - 1，这样 i 最大取到 m-2，nxt[i+1] 最大取到 nxt[m-1]，正好覆盖整个数组。这个边界条件没有技巧，就是多写几遍、多跑几个用例就能记住。

还有一个常见问题是模式串长度为 1 的情况。此时 build_next 返回的数组是 [-1]，匹配循环里能正常处理，但也要注意在 kmp_search 开头判断 m == 0 的情况——空模式串按惯例返回 0，这个边界很多人在笔试时会漏掉。

5.3 匹配结束后下一步该怎么走

有时候题目不是要求第一次出现的位置，而是统计出现次数。比如问 P 在 T 中出现了多少次，且允许重叠。这种情况下，匹配成功后不能直接返回，而是要让 j 回退到 nxt[j] 然后继续匹配。

def kmp_count(text, pattern): n, m = len(text), len(pattern) if m == 0: return 0 nxt = build_next(pattern) i, j = 0, 0 ans = 0 while i < n: if j == -1 or text[i] == pattern[j]: i += 1 j += 1 else: j = nxt[j] if j == m: ans += 1 j = nxt[j] return ans

其实这一行 j = nxt[j] 是统计重叠匹配的关键。比如模式串 "aaa" 在文本串 "aaaa" 中，如果不加这行，一找到匹配就停了，结果只有 1；加了之后，每次匹配成功就把 j 回退到最长相等前后缀的位置，也就是 2，这样能找到 2 个重叠的匹配。这是 string matching 类题目里非常常见的变体，值得单独记一下。

5.4 一个经常被忽视的问题：next 数组是逐个递推的，不要试图直接看整串

有些朋友看了 next[6] = 2 之后，会想当然地以为 next[7] 和 next[6] 有关联，甚至想直接看整串的前后缀。比如 P = "abacaba"，整体最长相等前后缀是 "aba"，长度 3，但这不意味着 next 数组里会有一个位置的值是 3。事实上，next 数组的每个值只依赖前面子串的相等前后缀关系，推导是递推的，而不是一次性看完整串。

理解这一点很重要，因为 KMP 的优化本质就是在递推过程中利用了之前已经算好的 next 值来加速，而不是每算一个位置都把前缀后缀全部重新比对一遍。build_next 的时间复杂度能够做到 O(m)，正是因为这个递推关系。

6. 横向对比：KMP 之外还有哪些字符串匹配思路

6.1 从 KMP 出发看 BM 和 Sunday

如果只刷题，KMP 基本够用。但实际工程里，像文本编辑器里的查找功能、IDE 里的全局搜索，用的是更快的匹配算法。BM 算法的思路是从模式串尾部开始比较，利用坏字符和好后缀两个规则来决定跳跃距离，在真实文本上平均性能比 KMP 更好。Sunday 算法更简单粗暴，它关注的是文本串中参与匹配的最后一个字符的后一个字符，根据这个字符在模式串中的位置决定跳跃距离。

对于普通开发者来说，理解这些算法的适用场景比记住实现更重要。KMP 在最坏情况下有稳定的 O(n+m) 表现，适合对时间复杂度有严格要求的场景；BM 和 Sunday 在平均情况下更快，但最坏情况下可能退化到 O(n*m)。日常刷题和面试中，掌握 KMP 是底线，有余力的可以再看看 Sunday，它的代码更短，某些场景下效率反而更高。

6.2 KMP 的变体应用：旋转字符串、重复子串判断

字符串匹配的经典变体题，我至少能想到两个。一个是"旋转字符串"问题：给定两个字符串 s 和 goal，判断 s 经过若干次左移右移之后能否变成 goal。做法很简单，检查 len(s) == len(goal)，然后看 goal 是否是 s+s 的子串即可，这本质上就是 KMP 的一次应用。另一个是"重复子串"判断：判断一个字符串是否由某个子串重复多次构成。更 tricky 的做法是用 KMP 求 next 数组，如果 len % (len - next[len]) == 0 且 len != next[len]，则存在重复子串。

第二道题的原理值得多说一句。next[len] 表示整个字符串的最长相等前后缀长度，如果该字符串由一个子串重复多次构成，那么 len - next[len] 就是这个基本子串的长度，并且 len 一定能被它整除。比如 "ababab"，next[6] = 4，len - next[len] 等于 2，len % 2 == 0，所以存在重复子串 "ab"。这个推导用到了 next 数组的核心性质，能想明白的话，对 KMP 的理解就真的到位了。

7. 实际刷题中的三个心得

7.1 手写推导比直接抄代码重要一百倍

我在最初学 KMP 的时候，直接看代码觉得懂了，但过三天再写就卡壳，尤其是 build_next 那段循环。后来我强迫自己在纸上手动推导 next 数组，从短串到长串，反复推了几轮，再回头写代码，发现顺了很多。代码是思想的表达，思想没建立起来，代码永远记不牢。

我有一个具体的方法，大家也可以试试。拿一个中等的模式串，比如 "ababaca"，先手动用笔算出 next 数组，然后在代码里让程序打印 next，两厢对照。一旦某一位对不上，就停下来仔细想为什么。这个过程很痛苦，但每一次卡壳都是在加深理解。

7.2 用极端用例验证思路

写完 KMP 的代码，我习惯先用几个极端用例测试：空字符串、模式串和文本串完全相同、模式串只出现一次且在所有位置都失配、模式串是单个字符、模式串里有大量重复字符。这些用例能暴露绝大多数边界错误。特别是大量重复字符的场景，比如 P = "aaaa"，T = "aaaabaaa"，如果 next 数组算错一位，效率就会退化到接近暴力解。

很多人在 LeetCode 上提交失败，报的往往就是"超出时间限制"，原因就是 next 数组写错了，导致匹配过程的回退逻辑失效，实际复杂度退化成 O(n*m)。一看到超时就该条件反射想到：是不是失配回退没有接住，导致文本串指针在反复比较同一个位置。

7.3 把一道题吃透比刷十道题有用

每日算法题系列做了这么久，我最大的感受是：覆盖知识点的方式不是求多，而是求透。像 KMP 这种经典算法，如果只是背模板，过一周就忘；如果能把 next 数组的推导逻辑、失配时的回退流程、代码的边界条件都搞明白，那么后面遇到类似的字符串匹配题，基本都能一通百通。

顺便再说一个小技巧，实际写代码的时候，给变量命名用 text、pattern、nxt 而不是 i、j、t，可读性会好很多。尤其是刷题后期回看笔记的时候，语义化的变量名能省不少力气。这不算什么高深经验，但确实是实际写代码时体会到的差异。