字符串匹配算法精讲：从暴力解法到KMP与滚动哈希的实战指南

1. 从“子串”这个题说起：它到底在考你什么

某在线评测平台上有一道编号为4018的字符串基础题，分类明确写着“字符串”。题干本身并不复杂：给两个字符串，模式串和文本串，前者短一些、后者长一些，要求判断模式串是否出现在文本串中，并且输出它出现的所有起始位置，或者总次数。我第一次看到这个题的时候觉得很眼熟，和很多教材里的经典字符串匹配练习题几乎一模一样，但真动手写了之后才发现，越基础的题越能暴露问题。有人忘记考虑重叠匹配，有人在模式串比文本串还长的时候直接越界，还有人明明用对了算法，却因为输出格式差一个空格反复提交。

所以这篇文章想做的，不只是给你一份能通过的代码，而是把这个题目背后牵出的概念、算法、边界情况和调试思路全部掰开揉碎讲一遍。无论你刚开始接触字符串处理，还是准备回顾匹配算法准备笔试，这篇文章都适用。我会从暴力解法讲起，再过渡到 KMP 和滚动哈希，最后集中整理我会在这个题上反复踩的坑。整个过程尽量用平时交流的口吻写，毕竟字符串题看起来简单，真正拉开差距的地方恰恰是大家通常忽略的细节。

这道题的核心是“在一个字符串里找另一个连续片段”，也就是子串匹配。别小看这五个字，它几乎是所有更复杂字符串算法的地基。文本编辑器里的查找功能、搜索引擎的关键词定位、日志系统里的敏感词筛选，底层都会遇到同样的问题。把基础题吃透以后，你会发现后面学 AC 自动机、后缀数组时顺畅很多，因为它们本质上都在解决不同约束下的“怎么找得更快”。

1.1 题面里的常见设定

这类题目通常会在输入部分给出两行，第一行是待查找的短串，也就是模式串，习惯记为 pattern；第二行是长串，也就是文本串，习惯记为 text。输出则要求列出每一次匹配到的起始下标，有的题从 0 开始数，有的题从 1 开始数，这一点必须提前看清楚，不然很容易出现“样例过了，一交全错”的情况。

我第一次实现这个题时，下意识以为找到第一个匹配位置输出即可，但题目实际要的是所有出现的位置。比如 text 是ababa，pattern 是aba，匹配会发生在下标 0 和下标 2，一共两次。只看题面的人很容易漏掉第二个匹配，尤其是当两次匹配区域有重叠时，比如 text 是aaaaa，pattern 是aa，你至少需要判断是按重叠方式计 4 次，还是不重叠方式计 2 次。这类约定直接决定算法里成功匹配后下一步怎么走，稍后我会专门展开。

评测平台的输入规模通常不会在题面里明说，但根据字符串分类下这个编号的常见风格，长度很可能达到十万甚至百万级别。这个信息比题目本身更重要，因为它直接表明暴力写法大概率会超时，你必须提前想好更优的匹配策略。我的习惯是拿到字符串题先看两个东西：字符串长度上限是多少，以及是否涉及多组输入。长度决定复杂度上界，多组输入则要求你在主循环里把初始化工作做好，否则上一组数据留下的状态会污染下一组结果。

1.2 子串不是子序列：连续性的关键

很多第一次接触字符串题的人会混淆两个概念：子串和子序列。子串要求字符在原文中连续出现，中间不能断开；子序列则只要求字符按原顺序出现，跳过的位置无所谓。举个例子，text 是abcdef，那么bcd是子串，ace是子序列但不是子串，因为a、c、e在原串里并不连续。

这个区别对题目很重要。如果题目要求判断子序列，那可以用贪心加双指针，一边扫 text 一边匹配 pattern，时间复杂度很低；但如果题目要求子串，双指针贪心就不成立了。你没法通过只记录“已经匹配到第几个字符”来判断一个连续子串是否出现，因为你不知道当前匹配段的起点在哪。正因如此，子串匹配才需要专门设计匹配算法，而不是简单地扫描一遍就能解决。

我在指导别人写题时喜欢让他们先手动模拟一遍：拿一支笔，在纸上画出 text 的每个字符，再拿另一个小块当成 pattern 去滑动。你很快就会注意到，暴力做法就是把 pattern 这个“小窗口”从左到右一格一格移动，每到一个新位置就逐字符比较窗口里的内容是否一致。这个朴素的窗口思想贯穿后面所有优化方案，KMP 也好、滚动哈希也好，本质上都是在优化窗口移动和比较的速度。

1.3 这道题背后真正考察的四个点

这题虽然叫“字符串”，但它考察的能力其实很综合。第一是问题拆解能力：你要能把“找子串”抽象成“比较两个等长片段是否相等”的基本操作。第二是复杂度意识：暴力解法正确无误，但大规模数据下不可行，你得判断什么场景该用什么算法。第三是边界处理能力：空串、超长模式串、完全相等、只有一个字符等特殊情况都必须覆盖。第四是调试效率：字符串题的错误样例往往不明显，而且一旦错在匹配计数或下标转换上，肉眼很难扫出来。

这四个点对一个工程师来说，比单纯记住某个算法更重要。很多人在刷题时背下了 KMP 模板，但换个题目背景就不会用，根本原因就是没理解模板里每一行代码到底在解决什么问题。所以这篇文章后面不会只给代码，还会解释每一步的逻辑，尤其是那些容易顺手写错的地方。理解了为什么这样做，你才可能在真正需要的时候做出合适的变体。

2. 暴力解法：第一直觉能用，但别急着交

先写暴力版本不是浪费时间，它是整个思考过程的起点。暴力解法很朴素：把 pattern 和 text 的每一个可能起点对齐，然后逐个字符比较。如果全部相等，就记录当前位置。这个思路的好处是几乎不会写错，非常适合用来确认自己对题意的理解是否正确。

2.1 双循环逐位比较，最直接的写法

暴力版核心代码很短，我第一版通常这样写：

#include <iostream> #include <string> #include <vector> using namespace std; vector<int> bruteForceMatch(const string& text, const string& pattern) { vector<int> positions; int n = text.size(); int m = pattern.size(); for (int i = 0; i + m <= n; i++) { bool matched = true; for (int j = 0; j < m; j++) { if (text[i + j] != pattern[j]) { matched = false; break; } } if (matched) { positions.push_back(i); } } return positions; }

这里最需要注意的就是循环边界i + m <= n。字符串的起点 i 从 0 开始，如果 pattern 长度为 m，那么最后一个可能的起点是 n - m，所以i + m <= n保证 i 不会越过这个位置。有些初学者习惯写成i < n，这样访问text[i + m]时一定会越界，轻则得到错误结果，重则直接运行时错误。

当 pattern 为空字符串时，这段代码会直接跳过所有匹配。关于空串要怎么处理，我放在后面的边界章节细说。现在先假设题目保证两个字符串都非空，这样我们能集中精力理解匹配逻辑本身。

2.2 三种典型数据规模下的耗时估算

暴力算法最坏情况发生在 text 和 pattern 高度相似但始终差一点的时候。比如 text 全是a，pattern 也几乎全是a，只在最后一个字符是b，那么外层每移动一次，内层几乎要比较完整个 pattern 才失败。比较次数就是文本长度乘以模式长度，也就是 O(n * m)。

我们拿实际数字感受一下：当 n 和 m 都是 1000 时，最坏比较次数是 100 万次，现代计算机眨眼就能跑完；当 n 和 m 都是 10 万时，最坏比较次数是 100 亿次，这就已经要跑几十秒甚至更久了；如果两边都到 100 万，最坏情况是 1 万亿次，完全不现实。所以题目一旦把长度放到十万以上，暴力解法基本可以判断为行不通。

做得多了以后，我拿到一个新字符串题会先在心里估算：如果 n 和 m 都在 1000 以下，暴力代码简单直接，优化反而容易写错，那就没必要用 KMP。如果 n 或 m 其中一个超过 10 万，就应该直接考虑线性算法。复杂度分析不是纸上谈兵，它决定了你会不会被第 10 组测试数据卡死。评测平台可不会因为你思路简单就手下留情，它们往往专门准备了极端数据来淘汰暴力方案。

2.3 暴力真正的价值：当基准

暴力解法虽然不能应对大规模数据，但它的正确性非常容易验证。我在写完 KMP 或滚动哈希之后，并不会直接把代码交上去，而是会先用随机数据把暴力版和高效版的结果做对比，两边输出完全一致再提交。这个方法我在后面专门讲调试时还会再提，这里先记住一个结论：暴力算法是验证其他算法是否正确的最好参照物。

另一个容易被忽略的价值是，暴力解法能帮你快速排查题意理解是否出错。比如你还没想清楚重叠匹配要怎么计，暴力代码写出来以后跑一遍样例，立刻就能看到自己默认的不重叠逻辑和题目要求是否一致。如果发现输出数量不对，先别急着检查匹配逻辑，极有可能是对“出现次数”的理解出了问题。

3. KMP 算法：用预处理把匹配时间降到线性

KMP 的全称是 Knuth-Morris-Pratt，三个人的名字放在一起。它出现在这个题目的高级解法里很合适，因为只涉及单个模式串匹配，而且数据规模一大，线性时间几乎是必须的。KMP 的核心想法一句话就能概括：已经匹配过的信息不要丢掉，失配时利用这些信息跳到更有意义的位置继续比较，而不是每次只往右挪一格从头再来。

3.1 先理解“失配后该退回到哪里”

用一个例子说明。text 是ababcabcab，pattern 是abcab。暴力匹配从 text 下标 0 开始，前三个字符aba中ab匹配，但第三个字符a和c不匹配。按照暴力逻辑，下一步要从 text 下标 1 重新开始。可是我们明明知道前两个字符是ab，而 pattern 的开头也是ab，这时候如果直接把 pattern 挪到下标 1，必然还能匹配前面的一部分，直接从头比较显然浪费了已知信息。

KMP 的思路是提前计算 pattern 每个前缀的“最长相等前后缀长度”。当前缀和后缀存在一部分相同时，失配后就可以把 pattern 向右滑动到能让这部分前缀重新对齐的位置。还是上面的例子，pattern 的ab这个前缀同时也是已经匹配文本段的ab后缀，所以失配后不需要把 pattern 移到 1，只需要把 pattern 往右移到让这个公共部分重新重合的地方，然后继续比较当前字符。这样做的效果是，文本串的指针永远不回退，整个扫描过程只需要遍历一次 text。

这里有一个容易绕晕的地方：KMP 并不直接计算“向右滑多少格”，而是计算 next 数组，表示“当匹配到 pattern 第 j 个字符失配时，j 应该回退到多少”。回退之后前面的字符天然匹配，继续往下比就可以了。很多模板喜欢用前缀函数 pi 数组表示同样含义，实际上是一样的东西，只是下标习惯不同。下面我会以 0 下标为基础讲解，这是最容易和现代编程语言对齐的方式。

3.2 next 数组是怎么算出来的

next 数组的定义是：对于 pattern 的前缀p[0..i]，它能找到的最长相等真前缀和真后缀的长度。所谓真前缀、真后缀，就是不能取整个字符串自己。比如 pattern 是aaaa，那么p[0..1] = "aa"的最长相等前后缀是"a"，长度为 1；p[0..2] = "aaa"的最长相等前后缀是"aa"，长度为 2。

计算过程不需要对每个前缀重新判断，而是利用之前已经算好的结果递推。核心代码这样写：

vector<int> buildNext(const string& pattern) { int m = pattern.size(); vector<int> pi(m, 0); for (int i = 1; i < m; i++) { int j = pi[i - 1]; while (j > 0 && pattern[i] != pattern[j]) { j = pi[j - 1]; } if (pattern[i] == pattern[j]) { j++; } pi[i] = j; } return pi; }

这段代码我第一次看的时候也觉得有点绕，后来找到个比较顺的理解方式。变量 j 是当前已经匹配好的前后缀长度。我想给位置 i 计算 pi[i]，本质上是想知道如果把当前位置的字符pattern[i]接到已有的前后缀后面，还能不能继续保持相等。如果不相等，就缩小 j，尝试次长的一段前后缀，直到相等或者 j 变成 0。这其实和后面匹配阶段失配时的处理逻辑完全一致，所以理解了这段，KMP 就理解了一大半。

举个例子，pattern 是ababac。计算到 i 等于 4 时，pi[3] 等于 2，也就是前缀abab的最长相等前后缀是ab。现在要处理 i 等于 4 的a，先把 j 设为 2，然后比较pattern[4]和pattern[2]，两个都是a，相等，所以 j 加 1，pi[4] 等于 3，意味着ababa的最长相等前后缀是aba。整个过程不需要从零开始重新比较，这就是递推的高效之处。

3.3 匹配阶段完整代码

匹配阶段同样维护一个指针 j，表示当前已经匹配上了 pattern 的前 j 个字符。每次读入 text 的一个新字符，如果和 pattern 第 j 个字符相等，j 加 1；如果不等，就沿着 next 数组回退，直到可以继续比，或者回退到 0。当 j 等于模式长度 m 时，说明找到了一个完整匹配，记录起始下标为i - m + 1，然后继续用 next 数组回退，避免漏掉重叠匹配。

vector<int> kmpMatch(const string& text, const string& pattern) { vector<int> positions; int n = text.size(); int m = pattern.size(); if (m == 0) { return positions; } vector<int> pi = buildNext(pattern); int j = 0; for (int i = 0; i < n; i++) { while (j > 0 && text[i] != pattern[j]) { j = pi[j - 1]; } if (text[i] == pattern[j]) { j++; } if (j == m) { positions.push_back(i - m + 1); j = pi[m - 1]; } } return positions; }

注意匹配阶段有两个j回退。第一个回退发生在字符失配时，作用是回到一个仍然可能匹配的位置；第二个回退发生在找到完整匹配后，作用就是处理重叠匹配。如果你的题目要求不重叠的匹配次数，那么第二个回退要改成j = 0，让匹配从当前位置之后重新开始。这个区别就是前面提到题意理解问题，代码上只是一行之差，结果却完全不同。

3.4 三个容易忽略的写法坑

第一个坑是下标 0 和 1 的混用。有些教材里 next 数组从下标 1 开始，代码里的判断条件也会相应变化。我不建议看一个版本的代码，又套着另一个版本的思路调试，很容易把自己绕晕。选定一种统一从 0 开始的下标约定，把 buildNext 和匹配阶段都建立在同一套约定上，逻辑就清晰很多。

第二个坑是空 pattern。buildNext 对空串会生成大小为 0 的数组，匹配阶段访问pattern[j]时 j 也是 0，理论上不会越界，但pi[m - 1]中 m 减 1 等于 -1，访问就会越界。所以我在匹配代码里一开始就特判了空 pattern。如果题目保证 pattern 非空，这个特判可以省略，但加上它不会影响正确性，反而能防止因数据约定变化而翻车。

第三个坑是 int 和 unsigned 的混用。text.size()返回的是无符号整数，如果直接用text.size() - pattern.size()作为循环条件，当 pattern 比 text 长时，这个值的二进制解释会变成一个非常大的正数，循环直接失控。我在写边界处理时通常会先把长度转成 int，再参与计算，避免这类隐蔽问题。

4. 滚动哈希和内置函数：实战中的另一种思路

KMP 的优点是稳定、无碰撞，但并不是唯一选择。字符串匹配还有一个非常实用的家方向：把字符串映射成整数，通过比较哈希值来判断两个子串是否相等。这就是 Rabin-Karp 滚动哈希思想。它的匹配过程中不需要像 KMP 那样跳来跳去，只需要计算一次模式串哈希，再顺着文本串滑动计算每个窗口的哈希值，时间上也是 O(n + m)。

4.1 Rabin-Karp 的原理与代码框架

原理其实可以理解成把一个字符串看成某种进制的大整数。比如字符只包含小写字母，我就把a到z分别看成数字 0 到 25，然后选定一个大于字符集大小的进制 BASE，一般取 31 或 131 都可以。字符串abc的哈希值就相当于0 * BASE^2 + 1 * BASE + 2，当然实际计算时会取模，防止数字太大。

滑动窗口时不需要每次重新计算整个窗口的哈希。假设当前窗口是text[i..i+m-1]，下一个窗口只是把最左边字符去掉、右边新增一个字符。所以新的哈希值可以通过旧哈希值用加减乘运算得到，这就是“滚动”的含义。为了去除最左边的字符，还需要提前算出BASE^(m-1)对模数取余后的值。

vector<int> hashMatch(const string& text, const string& pattern) { vector<int> positions; int n = text.size(), m = pattern.size(); if (m == 0 || m > n) return positions; const long long BASE = 31LL; const long long MOD = 1000000007LL; long long hashPattern = 0, hashWindow = 0, power = 1; for (int i = 0; i < m; i++) { hashPattern = (hashPattern * BASE + pattern[i]) % MOD; hashWindow = (hashWindow * BASE + text[i]) % MOD; if (i < m - 1) { power = (power * BASE) % MOD; } } for (int i = 0; i <= n - m; i++) { if (hashWindow == hashPattern) { bool same = true; for (int j = 0; j < m; j++) { if (text[i + j] != pattern[j]) { same = false; break; } } if (same) { positions.push_back(i); } } if (i < n - m) { hashWindow = (hashWindow - text[i] * power) % MOD; if (hashWindow < 0) hashWindow += MOD; hashWindow = (hashWindow * BASE + text[i + m]) % MOD; } } return positions; }

代码里的same循环是为了处理哈希碰撞。理论上不同字符串可能算出相同哈希值，极少数情况下会产生误判，所以哈希相等后要再做一次真正的字符串比较来确认。这样处理后，Rabin-Karp 在最坏情况下可能退化到和暴力一样的复杂度，但在正常数据上的表现非常接近线性，而且代码写起来比 KMP 直观得多。

使用哈希时选 BASE 和 MOD 有讲究。BASE 要保证和字符范围互质，不要比字符集小，否则不同字符会映射到同一个数。MOD 最好选一个大质数，比如 1e9+7，这样不同字符串发生碰撞的概率很低。还有一点，如果担心哈希碰撞，可以用两个不同模数分别计算，只有两个哈希都相等才确认匹配，这一招在很多题目里也能用，缺点是计算量翻倍。

4.2 标准库 find 也很好用，但要注意场景

如果只是想知道 pattern 是否在 text 中出现，C++ 标准库里的string::find是最省事的方案：

string text, pattern; cin >> text >> pattern; if (text.find(pattern) != string::npos) { cout << "found" << endl; } else { cout << "not found" << endl; }

标准库实现通常会结合多种优化策略，实际速度非常快。而且它返回的是第一个匹配位置，对绝大多数工程场景够用了。但放到这个题里就有点尴尬，因为题目往往要求输出所有位置，你需要循环查找，每找到一次还要从下一个位置开始继续找，写法变得繁琐，而且每次查找内部都重新做准备工作，整体效率反而未必比 KMP 高。

我认为这类基础题不太适合直接用find提交。不是因为不能用，而是因为刷题的目的是理解匹配过程本身。KMP 和 Rabin-Karp 的代码量都不大，亲手实现一遍以后，你对字符串匹配的敏感度会提升一个档次。而find是一个黑盒，用多了会让自己停留在“调包”层面。实际工作时我经常用find，毕竟效率和正确性都有保证，但作为学习，我更推荐先写一遍底层算法。

4.3 各方案横向对比

我把这三种常见方案的适用场景整理成一个表，方便在做题前快速决策：

在实际做题时，如果模式串只有一个，长度达到十万级别，我会优先用 KMP。如果模式串有多个，需要同时在一长串文本里查找，那么 KMP 不太好直接扩展，可以考虑 AC 自动机，或者把 Rabin-Karp 改进成多模式版本。如果题目里字符串长度很小，直接暴力即可，没必要为了炫技引入更复杂的代码，因为任何一点实现错误都会增加排查成本。

5. 边界与细节：WA 和 RE 都藏在哪里

字符串题目最容易出现的问题不是算法不会，而是边界条件没有处理好。我见过太多人把 KMP 模板背得滚瓜烂熟，结果提交后答案错误，最后发现是空字符串、重叠计数或者下标转换出了问题。这一节把常见的坑集中梳理一遍，并给出排查思路。

5.1 空串和长度倒挂

题目如果没有明确说字符串非空，那就要考虑 pattern 为空的情况。理论上有两种处理方式：一种认为空串是任意字符串的子串，出现位置从 0 到 n 每个位置都算一次；另一种认为题目不涉及空串，直接特判输出空结果即可。实际比赛中我倾向于先看题面有没有给字符串长度范围，如果明确长度大于等于 1，就完全不用关心空串。如果没给，稳妥做法是提前返回空结果，而不是让代码崩溃。

长度倒挂是另一种更常见的风险。pattern 比 text 还长时，它不可能成为 text 的子串，直接输出 0 或者不输出任何位置就行。但很多初版代码会在循环条件里写出未定义行为，尤其是用text.size() - pattern.size()这种写法，前文已经提到，无符号整数相减可能会得到一个巨大正数，导致循环完全失控。我在写代码时习惯先把长度转为 int 并用i + m <= n做比较，就能从根上避开这个问题。

5.2 重叠匹配与重复计数

这是最容易导致答案错误的地方。什么是重叠匹配？举个例子，text 为banana，pattern 为ana，从 0 开始数，第一次出现在下标 1，第二次出现在下标 3。细看会发现第一次匹配的后两个字符和第二次匹配的前两个字符是重合的，但它们是两次独立出现，因为它们对应不同的起始位置。

如果题目统计的是“出现次数”，一般默认就是按起始位置计数，允许重叠。KMP 代码里找到完整匹配后j = pi[m - 1]，正是为了让下一次匹配从重叠部分开始继续。如果你把它改成j = 0，得到的次数就是不重叠次数。比如 text 为aaaa，pattern 为aa，允许重叠时答案是 3 次，不允许重叠时答案是 2 次。这个差异要是不提前确认，写出来的代码在部分数据上必然出错。

5.3 读入、输出和评测机的约定

很多评测题目会提供多组测试数据，读入会持续到文件末尾，所以主循环要写成：

string text, pattern; while (cin >> pattern >> text) { vector<int> ans = kmpMatch(text, pattern); for (int i = 0; i < (int)ans.size(); i++) { if (i) cout << " "; cout << ans[i]; } cout << endl; }

注意这里我把 pattern 放前面读，因为在原始题面里模式串通常先输入。实际以你看到的题面为准，但处理多组输入时一定要记得每组之间把累积状态清空。如果使用了子串输出，还要留意输出格式是每行一个位置还是一行拼接输出。像我是按“空格分隔同一行”这种方式写的，空结果时会单独输出一个空行，这通常能被评测机接受，但如果题目明确要求什么也不输出，就需要做额外判断。

5.4 报错信息排查速查表

把常见的报错类型和原因整理成速查表，遇到问题时可以快速对照：

字符串题的诊断往往比普通题更依赖测试样例，因为错误输出可能只出现在极端边界。所以不要只盯着题目给的样例，要自己构造一些极端数据去验证。下面这一节我会分享我日常用的测试方法，这套方法不仅适用于本题目，对其他算法题也很有帮助。

6. 值得长期坚持的调试方法和扩展方向

到这里，算法本身已经讲完了。但我想聊一个平时很多人忽略的问题：怎么保证自己写的字符串代码在各类数据上都是对的。只看题目样例远远不够，必须主动做测试。我几乎每写完一个字符串匹配算法，就会立刻进入对拍模式。

6.1 用随机数据对拍

对拍就是同时跑一个可信的基准程序和当前写的程序，在大量随机数据上比较结果。对于这道题，基准程序就是暴力匹配。我会写一个简单的数据生成脚本，随机生成 text 和 pattern，长度可以从小到大逐渐增大，然后把暴力结果和 KMP 结果都输出到文件，再用脚本对比。只要两组结果在所有随机数据上都一致，我才会放心去提交。

除了随机数据，还要加入一些针对性的构造数据。比如 text 全为同一个字符，pattern 也全为同一个字符；pattern 的前缀和后缀高度相似；匹配恰好发生在 text 的最开头和最末尾；pattern 长度比 text 长 1；pattern 与 text 完全相等。这些特殊输入最容易暴露边界问题。

6.2 关注数据范围再选算法

我现在拿到字符串题的第一反应不是立刻写代码，而是先根据数据范围判断复杂度。如果 n 和 m 都在 1000 以内，暴力就很合理；如果达到一万，暴力勉强可以，但最好做好优化；如果超过十万，基本只考虑线性算法。这个方法看似简单，却能避免很多无意义的超时。顺便说一句，KMP 的空间复杂度是 O(m)，当模式串长度为百万时，内存占用也只有几 MB，完全不需要担心。滚动哈希则几乎不占额外空间，适合内存受限的场景。

我在模拟项目里测过一个长度五百万的文本串，暴力匹配跑了大概三分钟，KMP 几乎是秒出结果。差距这么明显，原因就在于暴力在遇到“最后一个字符才失配”这种数据时成本太高，而 KMP 的每个字符平均只会比较常数次。字符串题考复杂度意识不是没道理的，一个设计良好的算法能让规模五百万的数据在零点几秒内跑完。

6.3 从子串匹配扩展出去

这道题解决的是单模式串匹配问题，但它的思想可以延伸到很多方向。如果你要在同一个文本串里同时找多个模式串，每个模式串都跑一次 KMP，代价就是 m 个模式串造成的重复扫描文本。这时候应该考虑 AC 自动机，它把多个模式串合并成一棵 Trie 树，并借用了 KMP 的失配指针思想，一次扫描就能匹配出所有模式串。如果你只关心模式串在文本里的整体频率，还可以用 Z 函数，代码更短，专门解决“子串出现次数”这一类问题。

如果文本串本身不变化，但会有大量不同的模式串进来查询，那么预处理后缀数组加二分会是很强的方案。每次查询可以通过后缀排序后的数组快速定位目标子串的范围，在需要频繁查询的工程场景里非常实用。这里我不深入展开，但希望你看完本文后能建立起一个印象：基础匹配只是起点，后面的路还很长。

最后再分享一个我个人的小习惯：写完这种字符串题，我一定会把完整匹配次数、第一个匹配位置、最后一个匹配位置一次性验证一遍。因为这三个值分别对应了匹配流程、起始下标计算和重叠回退逻辑，能同时通过这三关，代码大概率就稳了。这道“子串”题正是我用这个方法反复验证过的基础题，每次重新实现，我都会再收获一点对字符串匹配的体会，建议你也试试。