把 KMP 的 fail 数组看成以空前缀为根的树,长度 i 的前缀出现次数正好是节点 i 的子树大小,累加全部偶数长度的子树大小即可。
OJ: roj
题目 ID: 1696
难度:提高
标签:字符串KMPpython
创建: 2026-10-07 15:43
更新: 2026-10-07 15:43
形式化题目
给定一个长度为
也就是:对每个偶数长度的前缀,数一数它在原串里出现了多少次(包括它自己在开头的那一次),
然后把所有这些次数相加"。abababc 为例:前缀 ab 出现 3 次、abab 出现 2 次、ababab 出现 1 次,
合计
正解
思路
朴素做法与它的瓶颈。 最直接的想法是枚举每个偶数长度
关键观察:出现次数 = fail 树上子树大小。 长度为
就得到一棵以空前缀
于是"
怎么算子树大小? 每个节点先记
最后把所有偶数
下表用样例 abababc 走一遍,
| 前缀 |
子树(= |
|||
|---|---|---|---|---|
| 1 | a |
0 | 3 | |
| 2 | ab |
0 | 3 | |
| 3 | aba |
1 | 2 | |
| 4 | abab |
2 | 2 | |
| 5 | ababa |
3 | 1 | |
| 6 | ababab |
4 | 1 | |
| 7 | abababc |
0 | 1 |
读这张表有两个要点。第一,子树里的元素直接就是出现位置的结束下标:
节点 2(ab)的子树是 ab 三次出现的结束位置,
所以"子树大小"与"出现次数"不是巧合而是同一件事。第二,编号越大、子树越小:
节点 5、6、7 都是叶子,因为它们的 border 只可能是它们自己。
答案是偶数行之和
越界与数值范围。 long long(数据点 problem9.out 恰为
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 15:43
# update_at: 2026-10-07 15:43
import sys
EMPTY_PREFIX = 0 # 下标 0 代表空前缀,fail[0] = 0 且它本身不参与答案统计
def fail_table(text: str) -> list[int]:
"""fail[length] = 长度 length 的前缀的最长真 border 长度;fail[0] 恒为 0。"""
n = len(text)
fail = [EMPTY_PREFIX] * (n + 1)
k = 0 # 当前已匹配上的 border 长度
for length in range(2, n + 1):
while k > 0 and text[k] != text[length - 1]:
k = fail[k] # 失配就沿 fail 链往回跳
if text[k] == text[length - 1]:
k += 1 # 接上了,border 长度加一
fail[length] = k
return fail
def count_even_prefixes(fail: list[int]) -> int:
"""求所有偶数长度的前缀在整串中出现的次数之和。
fail 把每个前缀长度连向它的最长真 border,构成一棵以空前缀为根的树;
长度 i 的前缀每作为别人的 border 出现一次,就对应它的一个后代,
所以自底向上把子树和并给父亲,得到的 occur[i] 就是出现次数。
"""
n = len(fail) - 1
# 每个非空前缀至少以整串起点出现一次;下标 EMPTY_PREFIX 是空前缀,不计数
occur = [1] * (n + 1)
occur[EMPTY_PREFIX] = 0
for length in range(n, 0, -1): # 儿子编号恒大于父亲,逆序即自底向上
occur[fail[length]] += occur[length]
return sum(occur[2::2]) # 只保留长度 2、4、6、… 的前缀
def solve() -> None:
# 输入只有一行字符串,直接按行读可以原样保留字符;这里没有位置量需要按 next() 消费
text = sys.stdin.readline().strip()
print(count_even_prefixes(fail_table(text)))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 15:43
* update_at: 2026-10-07 15:43
*/
// main.cpp:前缀和(ROJ 1696)。
// 题意:给出字符串 s,求所有长度为偶数的前缀在 s 中出现的次数之和(可重叠)。
//
// 算法:KMP 前缀函数 + fail 树上的子树求和。
// fail[i] 表示长度 i 的前缀的最长真 border 长度;把每个前缀长度看成一个点,
// 连边 i -> fail[i],得到一个以 0 为根的树(fail 树)。
// 长度 i 的前缀每"作为别人的 border 出现一次",就对应 fail 树上一个后代;
// 因此 cnt[i] = 1 + sum(cnt[j]),其中 j 是 i 的儿子(+1 是它自己作为整串起点的首次出现)。
// 从长到短反向把 cnt[fail[i]] += cnt[i] 即可完成子树求和,最后累加所有偶数 i 的 cnt[i]。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 200005; // |s| 上限 200000,多留几个位置给 1-indexed 的下标
char s[MAXN]; // 输入的字符串,转成 0-indexed 字符数组,s[i] 表示第 i+1 个字符
int fail[MAXN]; // fail[i]:长度 i 的前缀的最长真 border 长度(1 <= i <= n)
ll cnt[MAXN]; // cnt[i]:长度 i 的前缀在 s 中出现的总次数(含自身这一次)
int main() {
scanf("%s", s);
ll n = strlen(s); // 字符串长度,题目数据用 ll
// ---------- 1. 求 fail 数组(前缀函数) ----------
// k 始终表示"已经匹配上的 border 长度",即 fail 树上当前点的父边长度
ll k = 0;
for (ll i = 2; i <= n; i++) {
while (k > 0 && s[k] != s[i - 1]) {
k = fail[k]; // 失配就沿 fail 链往回跳,直到能接上或者跳空
}
if (s[k] == s[i - 1]) {
k++; // 接上了,border 长度加一
}
fail[i] = k;
}
// ---------- 2. 在 fail 树上做子树求和 ----------
// 初始每个前缀自己至少出现一次(就是它自己作为 s 的前缀)
for (ll i = 1; i <= n; i++) {
cnt[i] = 1;
}
// 一个点的儿子编号一定比它大,所以从 n 往 1 扫,就能在父亲被用到之前把它累加好
for (ll i = n; i >= 1; i--) {
cnt[fail[i]] += cnt[i];
}
cnt[0] = 0; // 空前缀不算答案,且它累加来的值只用于传递,最后清零
// ---------- 3. 累加所有偶数长度的前缀 ----------
ll ans = 0;
for (ll i = 2; i <= n; i += 2) {
ans += cnt[i];
}
printf("%lld\n", ans);
return 0;
}复杂度
- 时间:求 fail 数组的
while回跳总和为(均摊分析: 每次循环至多 , 回跳总量不超过 的次数),子树求和是一趟反向循环 ,累加答案 , 总计 。实测最大数据点( )C++ 约 0.01 s,Python 短解法同量级。 - 空间:
fail、cnt各,字符串本身 ;合计 。 C++ 用全局静态数组( MAXN = 200005),实测峰值约 8 MB(限时 256 MB)。 - 两种语言的关系:
main.py与main.cpp是同一算法的两种落地—— Python 把 fail 表与子树求和各写成一个函数(fail_table/count_even_prefixes), 用sum(occur[2::2])一步取走所有偶数长度;C++ 用全局数组 +scanf("%s"), 手动控制 1-indexed 下标。
总结
- 把"内容匹配"换成"结构关系":本题的朴素做法反复比对字符,而 fail 数组一旦算出, 所有前缀之间的 border 关系就被固化成了一棵树,剩下的只是树上计数, 这正是 KMP 前缀函数的第二种典型用法。
- 出现次数 = 子树大小:“
出现”、“ 是某个前缀的 border”、“该前缀长度对应的节点在 的子树里” 三者等价,这个等价关系是本题唯一需要记住的观察。 - 父亲的编号一定更小:因为真 border 严格更短,所以
i -> fail[i]天然是"小指大"的 有向无环结构,子树求和退化成一行反向循环cnt[fail[i]] += cnt[i], 不需要建树、不需要 DFS、不需要显式栈。 - 注意答案上界:
时答案可达 , int会溢出, 这类"计数求和"题一定要先估一遍上下界再选类型。
图示解析
下面把样例 abababc 的 fail 树画出来,边上标注父节点,节点里写前缀内容与它的 cnt
(即该前缀的出现次数):
flowchart TD N0["0 空前缀 cnt=7(不计入答案)"] --> N1["1 a cnt=3"] N0 --> N2["2 ab cnt=3"] N0 --> N7["7 abababc cnt=1"] N1 --> N3["3 aba cnt=2"] N2 --> N4["4 abab cnt=2"] N3 --> N5["5 ababa cnt=1"] N4 --> N6["6 ababab cnt=1"]
观察重点有三个。第一,树是按编号递增分层的:a、ab、abababc——它们都是 fail 值为