看到 P3618 这个编号刷题的人通常会有两种反应要么是“这什么冷门题”要么是“‘误会’这名字起得有点意思”。我第一次点开这道题的时候确实是被名字勾住了。字符串匹配本身不算难可题目叫“误会”多半是在提醒你什么——后来我切完题才明白真正让你翻车的不是算法多难而是名字底下藏着的那几个“误会”。这篇题解不整虚的直接把题目拆开它到底要算什么、为什么暴力跑不动、用哈希还是 KMP、代码怎么写、哪些边界细节能让你从 WA 调到怀疑人生。无论你现在学到 KMP 还是只会暴力匹配看完应该都能自己手写一遍。1. 先看题目它到底让我们做什么1.1 题目背景与任务定义P3618 这道题核心描述就一句话给你两个字符串 a 和 b统计 b 在 a 中作为连续子串出现的次数。注意两个关键词。第一是“连续子串”不是子序列。子序列可以跳过字符a “abc”b “ac” 也能算出现但子串必须是挨在一起的“ac” 在 “abc” 中并没有连续出现。第二是“出现次数”它按位置数不是按不重叠的块数数。这两个条件里藏着一半的“误会”。输入输出形式上一般会给第一行一个字符串 a长度记为 n。第二行一个字符串 b长度记为 m。要求输出一个整数表示 b 在 a 中出现的次数。如果题目没有特别说明大小写不敏感那 “A” 和 “a” 就是两个字符哈希时直接按 ASCII 原值参与计算不要手动转小写。这个坑虽然小但真的有人踩过。我直接用几个样例说明题意ab输出解释abcabcabcabc3位置 1、4、7 各命中一次aaaaaa3位置 1、2、3 各命中一次允许重叠helloworld0完全没有出现“aaaa” 中 “aa” 的输出是 3 不是 2这就是最常见的第一个“误会”。1.2 为什么暴力枚举一定会超时看到这道题第一反应大概率是枚举起点然后从每个起点往后逐字符比较int ans 0; for (int i 0; i m - 1 n; i) { bool ok true; for (int j 0; j m; j) { if (a[i j] ! b[j]) { ok false; break; } } if (ok) ans; }这写法对不对逻辑上完全正确但数据一上去就超时。怎么算出来超时的枚举起点有 n - m 1 个每个起点最坏比较 m 个字符总操作次数是 O(n * m)。如果 n 和 m 都到 10^6那么 n * m 10^12也就是一万亿次字符比较。哪怕一次比较 1 纳秒也要 1000 秒才能跑完更别说每次比较还带分支判断。拿生活里的事打个比方你要在一本一万字的书里找一个五千字的段落如果每个位置都从头把一个五千字段落念一遍等于一本书翻来覆去念了上千万字时间当然爆炸。所以题目真正的考点就是如何把复杂度从 O(n * m) 降下来。1.3 “误会”藏在哪两个细节里先说明文里最明显的“误会”重叠计数。很多人做字符串匹配的时候潜意识会觉得匹配成功以后下一个匹配位置必须从当前结束位置之后开始这是受了“不相交区间”思路的影响。但题目要的是位置数不是最大数量所以两个匹配可以在字符上有重叠。一个很经典的例子就是 a “aaaa”b “aa”正确输出 3不是 2。第二个“误会”是边界。如果 m n那么 b 在 a 中出现的次数一定是 0。虽然循环条件 l m - 1 n 会在这种情况下自动不成立理论上不会越界但如果你在代码里先算了 int r l m - 1又用 r 去访问 a[r]那下标就会变成负数或者越界导致一个莫名其妙的内存错误。处理这种题第一步永远是特判长度这是稳定拿分的开始。2. 算法选型哈希、KMP 还是 Z 函数2.1 字符串哈希为什么适合这道题字符串哈希的核心思想是把一个字符串看成一个 base 进制的大整数然后比较哈希值来判断两个字符串是否相等。比较的代价从 O(m) 降到了 O(1)预处理阶段把前缀哈希数组算出来后面所有子串查询都是常数时间。具体做法分几步预处理幂数组 pw[i]pw[i] pw[i-1] * base。预处理 a 的前缀哈希 h[i]h[i] h[i-1] * base a[i]。算出 b 的整体哈希 hb。枚举起点 l用区间哈希公式取出 a[l..r] 的哈希和 hb 比较。区间哈希公式是h(l, r) h[r] - h[l-1] * pw[r-l1]为什么长这样我给你推一遍。假设 base 131字符直接转成整数参与运算。字符串 “abc”哈希值就是 a * 131^2 b * 131 c。如果你想取出中间的 “bc”也就是 b * 131 c就需要把“abc”高位的 a 整个减去。h[3] 是完整的 “abc” 哈希h[1] 只是 “a” 的哈希那就要把 h[1] 乘以 131 的 2 次方因为中间隔了两个字符位置再从 h[3] 里减掉。这就是公式里 pw[r-l1] 的由来。用一个十进制类比就更清楚了在整数 12345 里取中间三位“345”就是 12345 - 12 * 1000。这里的 12 是前缀截断1000 是 10 的 3 次方。哈希公式和这个完全同理只不过进制是 base 而不是 10。base 一般取 131、13331、131313 这类质数含义是字符集规模加一个余量。如果字符只是小写字母26 个字符base 取 131 已经比字符集大很多能有效避免同一进制下小字符集常见的碰撞。2.2 KMP 方案不哈希也能做但细节更密KMP 是这题的另一条路而且从理论上看更“稳”它不会出现任何哈希碰撞。KMP 的做法是先对模式串 b 预处理 next 数组表示 b 的每个位置之前的最长相同前后缀长度然后用这个信息在匹配失败的时候快速跳转。KMP 匹配部分的核心逻辑是这样j 表示当前已匹配的 b 的前缀长度。遍历 a 的每个字符 a[i]。如果 a[i] 和 b[j] 相等j。如果 j 达到 m说明匹配成功一次记录答案然后 j next[j]。如果不相等j next[j] 继续尝试。这里有一个非常容易错的点匹配成功后j 的回退是 next[j] 而不是 0。为什么因为要支持重叠计数。比如 a “aaaa”b “aa”第一次匹配成功后 j 回到 next[2] 1也就是仍然保留一个已匹配前缀这样下一次判断才能把位置 2 的匹配也数进来。如果你习惯性写 j 0输出就会少算。KMP 看起来只要维护一个 next 数组但 next 数组本身又分两种常见写法一种是 next[i] 表示 i 之前的最长相等前后缀长度另一种是 next[i] 表示失配后跳转的位置。不同模板之间差一个下标背模板背岔了就会出现各种神秘 RE。相比之下写哈希的思维负担会小一些。2.3 三种方案横向对比把常用的可解题方案放在一起对比选型思路就清楚了方案预处理复杂度单次匹配耗时空间碰撞风险代码量朴素暴力无O(n * m)O(1)无最少KMPO(m)O(n)O(m)无中等字符串哈希O(n m)O(n)O(n)有可降低少Z 函数O(n m)O(n)O(n m)无中等如果题目只要求单模式串匹配KMP 和哈希都能过。哈希的优势在于代码短、思路直白而且后面扩展性更好。比如让你统计任意两个子串是否相等KMP 做不到哈希可以比如让你求最长回文子串哈希配合二分也能写出来。所以我的建议很明确这一题先学会哈希KMP 作为对拍验证工具去理解两套都会才是真的稳。Z 函数也可以做做法是把 b 和 a 拼接成 b 分隔符 a然后求每个后缀和整个串的最长公共前缀长度凡是长度等于 m 的位置就是一个匹配点。分隔符要选一个不会出现的字符防止匹配跨过边界形成假的相同前后缀。这个方法适合作为思路拓展但写起来没有哈希省心。3. 完整实现从哈希公式到 AC 代码3.1 单哈希自然溢出版先上最实用的版本用 unsigned long long 自然溢出。C 里 unsigned long long 相加乘多了会自动对 2^64 取模这相当于帮你省掉了模运算速度很快。#include bits/stdc.h using namespace std; using ull unsigned long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); string a, b; cin a b; int n (int)a.size(), m (int)b.size(); if (m n) { cout 0 \n; return 0; } const ull base 13331; vectorull pw(n 1, 1); for (int i 1; i n; i) { pw[i] pw[i - 1] * base; } vectorull h(n 1, 0); for (int i 1; i n; i) { h[i] h[i - 1] * base (ull)a[i - 1]; } ull hb 0; for (int i 0; i m; i) { hb hb * base (ull)b[i]; } auto get_hash [](int l, int r) - ull { // 注意这里 h 的下标从 1 开始原串下标从 0 开始 return h[r] - h[l - 1] * pw[r - l 1]; }; int ans 0; for (int l 1; l m - 1 n; l) { int r l m - 1; if (get_hash(l, r) hb) { ans; } } cout ans \n; return 0; }有几个地方我写的时候特意保留了注释pw 数组长度至少要到 n因为 get_hash 里要访问 pw[r - l 1]最大的情况是 r - l 1 m而 m 可能等于 n。原串下标从 0 开始前缀哈希 h 下标从 1 开始所以 a[i - 1] 的映射别漏了。cin 关闭同步之后1e6 长度的字符串输入完全够用不需要手动写 getchar 快读。这版代码在绝大多数数据下都能过常数也很小。3.2 双哈希版本要不要上什么时候上自然溢出有一个隐忧unsigned long long 的溢出本质是对 2^64 取模而 2^64 是一个合数不是质数。在某些极限数据下确实存在两个不同字符串哈希值相同的可能性。OJ 上的随机数据一般撞不上但如果你觉得这题的出题人有意卡哈希或者你是打正式比赛那就老老实实上双哈希。双哈希的常见组合两个模数比如 1e9 7 和 1e9 9。一个自然溢出一个模数。核心代码写成这样const long long MOD1 1000000007; const long long MOD2 1000000009; const long long base 131; pairlong long, long long h[N]; pairlong long, long long pw[N]; long long get_hash1(int l, int r) { return (h[r].first - h[l - 1].first * pw[r - l 1].first % MOD1 MOD1) % MOD1; }双哈希实质就是把两个不同模数下的哈希值拼成一个 pair只有 pair 的两个值都相等才认为字符串相等。两个独立的哈希系统同时碰撞的概率基本可以忽略不计。写双哈希要注意取模时的负数问题。C 的取模结果可能是负数所以计算区间哈希时需要加上 MOD1 再取一次模。这个模运算写多了确实拖慢速度但安全性和速度之间的取舍数据规模到了一定程度安全问题优先。3.3 复杂度分析与样例手算验证用哈希做法预处理的循环分别是 O(n) 和 O(m)匹配枚举也是 O(n)加起来是 O(n m)。空间上多了两个长度为 n 的数组也是 O(n)。对于 n m 10^6 的输入代码总操作量只有百万级别最多几十毫秒就能跑完。我拿一个容易算错的样例验证一下。a “ababab”b “aba”起点 1子串是 “aba”命中。起点 2子串是 “bab”不命中。起点 3子串是 “aba”命中。起点 4子串是 “bab”不命中。答案是 2。注意起点 1 和起点 3 的匹配在字符层面有重叠但都算一次。你可以在本地把暴力程序和哈希程序对拍一下用随机生成的小字符串跑 10 万组输出一致就说明基本没问题。4. 踩坑记录那些让你一个字符之差就 WA 的误会4.1 下标不统一是最隐蔽的 bug我写这个题的时候第一版代码是直接用 char 数组读的字符串下标从 0 开始。哈希数组 h 我又习惯性从 1 开始更新然后 get_hash(l, r) 里写了 h[r] - h[l - 1] * pw[r - l 1]看起来没错但实际跑起来样例都过不了。问题出在映射如果 h[i] 存的是 a 的前 i 个字符那么 h[1] 应该等于 a[0]但我写成了 h[i] h[i - 1] * base a[i]直接把 a[1]也就是第二个字符塞进了第一位。这种错在样例上往往只差一个字符肉眼根本看不出来。我的习惯是原串下标和前缀数组下标之间建立一个固定规则写死在注释里。用 string 时原串下标 0 到 n-1前缀哈希下标 1 到 n取字符用 a[i-1]用 char 数组时可以直接 scanf(%s, a 1) 让下标天然从 1 开始但 char 数组要开 N 2防止最后的空字符越界。4.2 自然溢出哈希真的绝对安全吗答案是否定的。unsigned long long 的溢出取模等价于把哈希值放在模 2^64 的剩余系里。理论上一定存在两个不同的字符串在模 2^64 意义下相同。只是以普通人的智力和算力构造这种碰撞需要很刻意的手段。日常 OJ 测试数据不会做这种针对所以单哈希在竞赛里经常能过。但如果你想彻底放心先写一版暴力程序再写一版 KMP最后写一版哈希三个程序对拍一万组随机数据。如果哈希输出和其他两个不一致先别急着下单哈希——大概率不是碰撞而是你的区间公式写错了。碰撞发生的概率极低反而是代码逻辑的 bug 更常见。真被卡哈希时双哈希是首选解药没有之一。别去试图找一个“天选模数”没有这种东西。4.3 输入输出的性能陷阱字符串长度到 10^6 时cin 默认和 stdin 同步会逐个字符检查缓冲区速度极慢。解决办法很简单ios::sync_with_stdio(false); cin.tie(nullptr);这两行写在 main 开头之后 cin 的效率能提升一个数量级。如果你不用 C 流直接用 scanf 也行。真正要避免的是“cin 不关同步”和“getchar 手写快读却没处理好换行”两种极端。有个小细节如果题目有多组数据读字符串时要注意每行末尾的换行。用 cin 和 string 时没有这个问题但如果你自己写快读就必须在每次读完数字后把换行吃掉。这个问题我在别的字符串题里踩过一次 RE 排查了半小时最后发现是 getchar 吞掉了一个负数字符。4.4 实用问题速查表症状可能原因解决办法样例 aaaa / aa 输出 2匹配成功后又跳回 j 0回退改成 j next[j]输出答案总是少 1枚举起点时少算了最后一个位置循环条件写成 l m - 1 n哈希值出现负数区间哈希计算中没有归正加上模数再取模下标越界char 数组开得太小开到 N 2至少比长度大一无故超时cin 没有关闭同步加 ios::sync_with_stdio(false)输出完全混乱字符串读入时把换行读成了数据自己写快读时注意吃掉换行这张表其实不只是 P3618 适用所有字符串哈希题、KMP 题都能用上。我每次写字符串题之前都会把这几个点过一遍能省下很多调 bug 的时间。4.5 多组数据场景下的内存与初始化还有一种常见附加情况题目不给单组数据而要求读到 EOF对每组都输出答案。如果每次都重新建立 vector 的 pw 和 h代码写得直观但有点浪费。更高效的做法是开全局数组按当前长度只计算到 n 即可。但要注意如果上一组数据长度比较大当前组长度比较小残留的旧 pw 和 h 不会影响你因为你只访问当前长度范围内的下标。真正要小心的是模式串 b 的哈希 hb。如果这组数据里 b 的长度为 0或者 b 就是一个空串——字符串题中一般不出现但如果出现了hb 初始化成 0而所有长度为 1 的子串哈希都不为 0答案会变成 0这反而符合空串在普通定义下“不参与匹配”的习惯。我建议遇到这种边界直接输出 0不要硬算。另外答案的计数器用 int 其实够用因为最多出现 n - m 1 次n 在 10^6 范围内不会超 int。但为了保险我一般直接写 long long反正多那 4 字节也没什么代价。防御性编程的习惯就是在这些小地方一点一点养起来的。5. 最后说点自己的做题体会这道题让我最触动的不是算法本身而是它的名字。字符串匹配里的“误会”其实就是把“看似显然”当成“正确”把“重叠计数”当成“必须跳过”把“单哈希不会错”当成“永远不能错”。做题如此写代码也一样——很多问题都是在你觉得“理所当然”的那一刻埋下的。我看代码的习惯是每写完一个关键函数就在旁边注释一行公式。区间哈希公式我写完直接用但每次都需要把 base 的幂次和下标重新核对一遍。这个习惯让我后来面对回文、子串比较这类题目基本能直接复用前缀哈希的模板不用重新推一遍。如果你手里还有其他字符串匹配的题建议用这道题的哈希模板去刷两三道类似题比如统计所有不重叠出现次数、或者查询两个子串是否相等。哈希这套东西你真正写熟了才知道它有多顺手。P3618 本身不是难题但它值得你停下来想一想“为什么会误会”这件事。