聊一聊洛谷 P7114 [NOIP2020] 字符串匹配。当年 NOIP 提高组这道题出得非常有意思一部分人觉得它是白送的签到题另一部分人却被卡到比赛结束都没调出来。核心原因在于这题的数据范围给得很大胆单组字符串长度不超过 2^20所有测试点字符串总长也不超过 2^20时间复杂度稍微算错一个常数或者实现里多一重循环就会被 TLE 教做人。我个人认为这道题最值得写的不是 Z 函数本身而是“把复杂的字符串拆分条件逐步转化成计数问题”的思考过程。这篇文章适合三种人第一种是 NOIP/省选备赛的选手想彻底搞懂 P7114 的正解和常见坑点第二种是学过 Z 函数和前缀异或但不知道这类题怎么组合使用的人第三种是已经用哈希过了这题但不确定自己做法是否会被 Hack 的选手。我会把数学推导、代码实现、时间复杂度优化、常见 WA 原因全部讲清楚最后给一份可以直接提交的 C 代码。1. 题意拆解先把字符串分割问题变成计数问题1.1 题目到底在问什么题目要求把一个长度为 n 的字符串 S 写成这种形式S (AB) ^ k C其中A 和 B 都是非空字符串C 也是非空字符串(AB)^k 表示 AB 这个串连续重复 k 次k 是正整数设 f(X) 表示字符串 X 中出现次数为奇数的字符种类数。要求 f(A) f(C)统计满足条件的不同拆分方案数。这里有个关键理解一对 (A, B, C, k) 算一种方案。更准确地说题面其实是在问存在多少种“给字符串分段”的方式。很多人一开始会把 AB 看成不可拆的整体但实际 AB 内部还要再分 A 和 B所以方案数是由 AB 长度、A 的长度、以及循环次数 k 共同决定的。这个题意有一个容易忽略的点AB 是一个完整的前缀块整个串被切成“若干个相同的 AB 块”加上一个后缀 C。所以第一步一定是枚举 AB 块的长度 len再考虑这个块最多能重复几次最后考虑 A 在这个块内部怎么截。1.2 核心转化枚举 AB 块长度设 T AB那么 T 其实就是 S 的一个前缀长度记为 len。原问题等价于选一个 len满足 2 len n - 1选一个循环次数 k满足 k * len n - 1在 T 内部选一个 A 的长度 p满足 1 p len - 1要求 f(A) f(C)其中 C 是 S 去掉前面 k 个 T 后剩下的后缀统计所有合法的 (len, k, p) 组合数量。为什么要枚举 AB 块长度而不是直接枚举 A因为 A 只是 AB 内部的前缀AB 块本身必须满足“能重复 k 次”这是一个关于 len 和 k 的周期性问题和 p 是相互独立的。一旦确定 len 和 kAB 块就是固定的C 也是固定的剩下只需要在 AB 块内部枚举 p。1.3 奇偶性公式推导字符奇偶性最方便的处理方式是把每种字符出现奇偶性压成一个 mask。字符串 S 一共有 26 个小写字母所以用一个 26 位的整数 mask 表示“每个字符出现次数是否为奇数”。记pre[p] 表示 S 的前缀 S[0..p-1] 的奇偶性 maskblock[len] 表示 T S[0..len-1] 的奇偶性 masktotal pre[n] 表示整个 S 的奇偶性 mask。首先T 重复 k 次之后整个 (AB)^k T^k 的奇偶性 mask 是多少两个相同字符串拼接相同字符的出现次数会变成原来的两倍奇偶性会相互抵消。所以 T 重复一次产生 block[len]重复两次变成 0重复三次又变回 block[len]。换句话说mask(T^k) (k 是奇数) ? block[len] : 0这个结论是整道题的突破口。因为 S T^k C所以 C 的奇偶性 mask 等于 total 异或上 T^k 的奇偶性 maskmask(C) total ^ mask(T^k)而 A 是 T 的前 p 个字符所以mask(A) pre[p]注意 mask(A) 和 k 完全无关只取决于 A 在前缀里的位置。于是条件 f(A) f(C) 变成popcount(pre[p]) popcount(mask(C))到这里问题就清晰了。固定 len 之后我们需要知道 len 能循环多少次并且对于每个可能的循环次数 k统计在 p 属于 [1, len-1] 这个范围内有多少个 pre[p] 的 popcount 不超过 popcount(mask(C))。2. 用 Z 函数快速求出每个长度的最大循环次数2.1 Z 函数是这道题的钥匙判断“一个前缀 T 从开头开始最多能连续重复多少次”最直接的工具是 Z 函数Z-algorithm。Z 数组的定义很简单z[i] 表示 S 和 S[i..n-1] 的最长公共前缀长度。其中 z[0] 一般直接设为 n。为什么它和循环节有关如果 S 的前 m 个块都是 T也就是 S[0..m*len-1] T^m那么从位置 len 开始的后缀前 (m-1)*len 个字符一定也等于 T^(m-1)。换句话说z[len] 至少是 (m-1)*len。反过来如果 z[len] (m-1)*len就说明从 len 开始连续 (m-1)*len 个字符和 S 开头相同自然可以推出 T^m 成立。所以T^m 成立当且仅当 z[len] (m-1)*len这个等价关系非常重要它把“某个前缀能循环多少次”变成了一个 O(1) 判断。Z 函数的模板如下void get_z(const string s) { int n (int)s.size(); z[0] n; for (int i 1, l 0, r 0; i n; i) { if (i r) z[i] min(r - i 1, z[i - l]); while (i z[i] n s[z[i]] s[i z[i]]) z[i]; if (i z[i] - 1 r) { l i; r i z[i] - 1; } } }理论上 Z 函数的均摊复杂度是 O(n)因为 while 循环里每次比较成功都会让右端点 r 单调前进整体比较次数不超过 2n。这里l, r维护的是当前已匹配到的最右区间初始为空代码里要注意z[i - l]只有在i r时才合法。2.2 为什么用 Z 函数而不是哈希或 KMP这道题网上流传的题解里有很大一部分是用字符串哈希过的。确实枚举 len再用哈希判断下一个 len 块是否等于前缀暴力扩展总循环次数大约是 n / 1 n / 2 ... n / n O(n log n)在 n 2^20 时大约是 2000 万次看起来完全能跑。但问题是单哈希可以被构造数据卡掉。NOIP 2020 中很多标程做法被卡过因为出题人确实考虑到了哈希暴力。如果你只用一个自然溢出哈希可能有极低概率撞车如果用双哈希虽然稳了但常数变大2000 万次哈希取模操作在 1 秒时限内很危险。Z 函数是确定性的线性复杂度不存在碰撞风险写起来也不比哈希麻烦。也有人用 KMP 的前缀函数做循环判断。KMP 判断某个长度 L 的前缀是否以 len 为周期用的是结论如果 L % (L - pi[L-1]) 0那么该前缀存在 len 周期。但 KMP 需要预处理前缀函数然后枚举 len 和 k复杂度也是 O(n log n)判断本身是 O(1)逻辑上没问题。不过 Z 函数天然适合“某个后缀和整个串的 LCP”这种查询代码更直观所以我个人推荐 Z 函数。2.3 最大循环次数的边界约束有了 z[len]还不能直接得出最大循环次数。因为有两个限制T^m 必须真的能循环出来也就是 m z[len] / len 1C 必须非空也就是 m * len n - 1所以 m (n - 1) / len。两个限制取最小值maxK min(z[len] / len 1, (n - 1) / len)这里有一个容易踩的坑第二个约束用 n - 1不是 n。因为 k * len 必须严格小于 n不能让 C 变成空串。很多人写的时候顺手写成了n / len结果边界数据全部 WA而且这种错误还不容易拍出来因为只有当 C 恰好为空的时候才会炸。再举个小例子验证S abababacan 9。取 len 2z[2] 等于 4因为 S[2..] ababaca和 S 的 LCP 是 abab 共 4 个字符。z[2] / 2 1 3(n-1)/2 4所以 maxK 3。也就是说 AB 块 ab 最多重复 3 次得到 ababab剩下的 C aca 非空。如果只凭 (n-1)/len 算出 4就会错误地把 abababab 也算进去这时 C a但 S 的第 8 个字符是 c 并不是 b根本不满足循环条件。3. 把计数优化到 O(26n)奇偶合并是关键3.1 暴力枚举 j 的复杂度陷阱很多初学题解的人第一版代码会写成这样for (len 2; len n; len) { int maxK min(z[len] / len 1, (n - 1) / len); for (int k 1; k maxK; k) { int maskC (k 1) ? (total ^ block[len]) : total; int need popcount(maskC); int sum 0; for (int p 1; p len; p) { if (popcount(pre[p]) need) sum; } ans sum; } }这个写法正确性没问题但复杂度是 O(n^2 log n)n 稍微一大就完全跑不动。稍微聪明一点把内层 p 的枚举换成桶和前缀和复杂度会变成 O(n log n * 26)。表面上看 n log n 约 2000 万再乘 26 就是 5 亿在 1 秒时限内一定 TLE。所以优化的核心是不能让每个 k 都做一次统计。必须想办法把循环次数 k 的枚举压缩成 O(1) 或 O(2)。3.2 按奇偶性合并循环次数回到公式mask(C) total ^ (k 为奇数时异或 block[len]k 为偶数时异或 0)也就是说无论 k 取多少mask(C) 只可能有两种情况k 为奇数mask(C) total ^ block[len]k 为偶数mask(C) total所以对于同一个 len所有奇数 k 对应的统计条件完全相同所有偶数 k 对应的统计条件也完全相同。我们不需要枚举每个 k只需要知道在 maxK 个连续的循环次数里奇数有多少个偶数有多少个。连续整数 1..maxK 中奇数的个数是 (maxK 1) / 2偶数的个数是 maxK / 2于是每个 len 只需统计两次ans 奇数个数 * 满足 f(A) popcount(total ^ block[len]) 的 A 数量ans 偶数个数 * 满足 f(A) popcount(total) 的 A 数量这是把 O(n log n) 降成 O(n) 的关键一步。很多 AC 代码其实都用了这个合并技巧但没有明说为什么可以合并这里必须讲透。3.3 动态桶和前缀和现在还需要快速回答对于当前 lenA 的长度 p 可以取 1..len-1在这么多前缀里有多少个 pre[p] 的 popcount need因为字符集只有 26 个字母pre[p] 的 popcount 范围是 0..26。我们可以维护一个桶 cnt[x]表示当前已经加入的 A 候选里popcount 恰好等于 x 的前缀个数。随着 len 从 2 增加到 n-1A 可取的范围也会扩大。处理完 len 之后下一个 len1 会允许 p 取到 len所以需要在进入下一轮之前把 p len 这个前缀加入桶里。换句话说len 2 时A 只能取 p 1len 3 时A 能取 p 1, 2len 4 时A 能取 p 1, 2, 3。所以每次循环开头先把 pre[len-1] 加入桶然后这个桶就正好代表 p 属于 [1, len-1] 的所有情况。查询时由于 popcount 的范围很小可以维护一个前缀和数组 pref[x]pref[x] cnt[0] cnt[1] ... cnt[x]那么“popcount need”的前缀数量就是 pref[need]。由于 cnt 数组只有 27 个元素每次加入一个新元素后重建一遍 pref复杂度是 O(26)非常小。总复杂度 O(26n)对于 n 2^20 大约 2700 万次简单操作加上 Z 函数的线性时间1 秒是能稳稳通过的。4. 完整代码实现与逐段注释4.1 可直接提交的 C 代码下面这份代码是我调试过很多次的版本复杂度 O(26n)空间 O(n)满足所有测试点总和不超过 2^20 的限制。这里直接给出完整实现#include bits/stdc.h using namespace std; const int MAXN (1 20) 5; int z[MAXN]; int preMask[MAXN]; int cnt[30], pref[30]; void get_z(const string s) { int n (int)s.size(); z[0] n; for (int i 1, l 0, r 0; i n; i) { if (i r) z[i] min(r - i 1, z[i - l]); while (i z[i] n s[z[i]] s[i z[i]]) z[i]; if (i z[i] - 1 r) { l i; r i z[i] - 1; } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { string s; cin s; int n (int)s.size(); get_z(s); preMask[0] 0; for (int i 1; i n; i) { preMask[i] preMask[i - 1] ^ (1 (s[i - 1] - a)); } int totalMask preMask[n]; memset(cnt, 0, sizeof(cnt)); memset(pref, 0, sizeof(pref)); long long ans 0; for (int len 2; len n - 1; len) { // A 的长度 p 可取 1..len-1 int pc __builtin_popcount(preMask[len - 1]); cnt[pc]; pref[0] cnt[0]; for (int i 1; i 26; i) { pref[i] pref[i - 1] cnt[i]; } int blockMask preMask[len]; // AB 块的奇偶性 mask int maxK min(z[len] / len 1, (n - 1) / len); // 奇数循环次数C 的奇偶性 total ^ block int needOdd __builtin_popcount(totalMask ^ blockMask); // 偶数循环次数C 的奇偶性 total int needEven __builtin_popcount(totalMask); long long oddCnt (maxK 1) / 2; long long evenCnt maxK / 2; ans oddCnt * pref[needOdd]; ans evenCnt * pref[needEven]; } cout ans \n; } return 0; }4.2 代码里的几个细节第一preMask 的下标表示前缀长度。preMask[i] 存的是 S[0..i-1] 这个前缀的奇偶性 mask。所以在循环里preMask[len]正好是 AB 块整体的 mask而preMask[len-1]是 p len-1 时 A 的 mask。每次进入新一轮 len把 preMask[len-1] 加入桶正好表示 A 可以取长度为 len-1 的前缀。第二__builtin_popcount 在 GCC 下可以直接用计算的是整数二进制中 1 的个数。因为 mask 最多用到 26 位用 int 存储完全够。第三ans 必须用 long long。最坏情况是字符串全为同一个字母比如 2^20 个 a。此时很多 len 和 p 都会满足条件方案数大约是 O(n^2 log n) 级别。实测全 a 字符串、n 1e6 时答案在 10^11 左右int 会直接溢出。所以看到答案范围不确定的计数题优先开 long long 总是对的。第四Z 函数里 z[0] n但没有被使用因为我们要查的是 z[len]而 len 至少是 2。Z 数组下标从 0 到 n-1代码里 z[len] 在 len n-1 时都合法。循环len n-1保证了这一点。5. 常见问题与避坑速查5.1 从 WA 到 AC 的常见原因我把自己和身边人在这道题上踩过的坑整理成了一张表方便直接对照排查现象原因解决方法答案偏大WA 在边界数据C 为空的情况被算入上限误写成 n/len上限必须写成 (n-1)/len答案偏小len2 时没统计A 或 B 为空被排除后没正确设置 len 起点len 从 2 开始A 长度从 1 到 len-1答案爆 int随机数据就 WA计数规模超过 2^31ans 开 long longTLEn1e6 超时每个 k 都做了一次 O(26) 查询按奇偶合并每个 len 只查两次多组数据之间互相污染桶 cnt 没有清空每组数据 memset用了单哈希被 Hack哈希碰撞被构造数据卡掉换 Z 函数确定性算法5.2 多组数据和初始化这题是多组测试所有测试点字符串总长不超过 2^20所以一个很常见的错误是上一组数据的桶和前缀和没有清空导致当前的统计包含了上一组字符串的前缀。解决办法是在每组数据开始前memset(cnt, 0, sizeof(cnt)); memset(pref, 0, sizeof(pref));preMask 和 z 数组不需要手动清空因为它们只按下标写入每组数据内都会被重新覆盖。cnt 和 pref 则必须清零因为它们是从空桶开始累加的。还有一个细节cnt和pref只有 30 个元素memset的代价非常小放心用。5.3 用对拍验证公式奇偶性公式虽然看起来简单但在比赛紧张时很容易把total ^ block写反或者搞混奇偶对应的 mask。我建议写一个暴力对拍程序来验证。暴力程序直接三重循环枚举 len、k、p然后分别计算 mask(A) 和 mask(C) 的 popcount 比较即可。不用做任何优化因为只用来对拍小数据。随机生成长度 1 到 20 的字符串比较暴力程序和优化程序的输出。对拍没问题之后再提交正解。我自己写的时候发现一个很隐蔽的问题用暴力程序对拍小数据暴力里如果也把 k 从 1 枚举到 maxK但 maxK 的计算方法和正解不同很容易两边错到一起去。所以暴力程序最好老老实实按题意枚举拆分点逐块检查是否等于 AB 块这样才是一个完全独立的参考实现。6. 写在最后的一点个人经验这道题给我的最大启发是当一个问题里同时出现“相同字符串重复若干次”和“奇偶性统计”时可以把它们拆成两个完全独立的维度。前者用 Z 函数解决后者用 mask 和桶解决最后只需要在枚举 AB 块长度时把它们组合起来。我在实际调试中还有一个实用的小技巧先写一个不优化的版本把所有满足条件的 (len, k, p) 直接输出观察规律。比如看到 len 固定时k 的奇偶性决定 C 的 mask然后再做合并优化思路就会非常顺畅。如果你正在备战算法竞赛遇到这种字符串计数的难题不妨也试试“先暴力验证直觉再逐步优化”的流程比直接硬想优化要高效得多。P7114 这题本身并不要求你掌握什么偏门算法Z 函数是基础内容奇偶性 mask 也是常见套路但把它们组合起来并且把枚举复杂度压到 O(26n)就是一道很有区分度的好题。希望这篇题解能帮你彻底摆脱对这题的“模拟赛噩梦”印象。