前缀和

GitHub跳转原题关系图返回列表

把 KMP 的 fail 数组看成以空前缀为根的树,长度 i 的前缀出现次数正好是节点 i 的子树大小,累加全部偶数长度的子树大小即可。

OJ: roj

题目 ID: 1696

难度:提高

标签:字符串KMPpython

创建: 2026-10-07 15:43

更新: 2026-10-07 15:43

形式化题目

给定一个长度为 nn 的字符串 ss,下标从 00 起。对每个偶数长度 i∈{2,4,… }i \in \{2, 4, \dots\}, 记 Pi=s[0..i−1]P_i = s[0..i-1] 为长度为 ii 的前缀,occ(i)occ(i) 为 PiP_i 作为 ss 的连续子串出现的次数 (允许重叠,同一个起点只算一次)。要求

answer=∑2⩽i⩽ni 为偶数occ(i).\text{answer} = \sum_{\substack{2 \leqslant i \leqslant n \\ i \text{ 为偶数}}} occ(i).

也就是:对每个偶数长度的前缀,数一数它在原串里出现了多少次(包括它自己在开头的那一次), 然后把所有这些次数相加"。n⩽200 000n \leqslant 200\,000,答案最大到 101010^{10} 量级, 以样例 abababc 为例:前缀 ab 出现 3 次、abab 出现 2 次、ababab 出现 1 次, 合计 3+2+1=63 + 2 + 1 = 6。

正解

思路

朴素做法与它的瓶颈。 最直接的想法是枚举每个偶数长度 ii,再枚举起点 pp 逐字符比对 s[p..p+i−1]s[p..p+i-1] 与 s[0..i−1]s[0..i-1],复杂度 O(n2)O(n^2) 甚至 O(n3)O(n^3),n=2×105n = 2 \times 10^5 下必然超时。 问题出在"每次比对一个前缀都要从头验证一遍内容"——而前缀之间的内容关系, KMP 的前缀函数(fail 数组)早就已经算出来了。

关键观察:出现次数 = fail 树上子树大小。 长度为 ii 的前缀在位置 pp 处出现, 等价于说:s[0..i−1]s[0..i-1] 是 prefixp+i=s[0..p+i−1]\text{prefix}_{p+i} = s[0..p+i-1] 的一个 border, 也就是 ii 是长度 p+ip+i 这个前缀的一个 border 长度。而 fail 数组给出的正是 “每个前缀的最长真 border”,把它当作父亲指针

parent(j)=fail[j],parent(0)=0  (j⩾1),\text{parent}(j) = fail[j], \qquad \text{parent}(0) = 0 \;(j \geqslant 1),

就得到一棵以空前缀 00 为根的树,通常称为 fail 树。 沿 failfail 链反复跳 parent,恰好能枚举出 jj 的全部 border 长度—— 也就是说

i 是前缀 j 的 border 长度  ⟺  i 是 j 在 fail 树中的祖先(含 j 自身).i \text{ 是前缀 } j \text{ 的 border 长度} \iff i \text{ 是 } j \text{ 在 fail 树中的祖先(含 } j \text{ 自身)}.

于是"PiP_i 出现在位置 pp"(即 ii 是前缀 p+ip+i 的 border)与"p+ip+i 落在 ii 的子树里" 是同一件事,而 p↦p \mapsto 结束位置 p+ip+i 是一一对应的,所以

occ(i)=∣{ j:i 是 j 的祖先 }∣=fail 树中 i 的子树大小.occ(i) = \bigl|\{\, j : i \text{ 是 } j \text{ 的祖先} \,\}\bigr| = \text{fail 树中 } i \text{ 的子树大小}.

怎么算子树大小? 每个节点先记 cnt[i]=1cnt[i] = 1(它自己:整串起点那一次出现), 然后自底向上把儿子并给父亲:cnt[parent(i)]+=cnt[i]cnt[parent(i)] \mathrel{+}= cnt[i]。 由于 parent(j)=fail[j]<jparent(j) = fail[j] < j(真 border 严格短于自身),父亲的编号一定比儿子小, 所以只要让 ii 从 nn 倒着扫到 11,就天然满足"儿子先处理、父亲后处理", 一趟 O(n)O(n) 的反向循环就能完成整棵树的子树求和,不需要显式建树、也不需要 DFS。

最后把所有偶数 ii 的 cnt[i]cnt[i] 加起来就是答案(i=0i = 0 表示空前缀,不参与统计)。

下表用样例 abababc 走一遍,n=7n = 7:

ii 前缀 PiP_i fail[i]fail[i] 子树(= PiP_i 的出现位置集合) cnt[i]=occ(i)cnt[i] = occ(i)
1 a 0 {1,3,5}\{1, 3, 5\} 3
2 ab 0 {2,4,6}\{2, 4, 6\} 3
3 aba 1 {3,5}\{3, 5\} 2
4 abab 2 {4,6}\{4, 6\} 2
5 ababa 3 {5}\{5\} 1
6 ababab 4 {6}\{6\} 1
7 abababc 0 {7}\{7\} 1

读这张表有两个要点。第一,子树里的元素直接就是出现位置的结束下标: 节点 2(ab)的子树是 {2,4,6}\{2, 4, 6\},正是 ab 三次出现的结束位置, 所以"子树大小"与"出现次数"不是巧合而是同一件事。第二,编号越大、子树越小: 节点 5、6、7 都是叶子,因为它们的 border 只可能是它们自己。

答案是偶数行之和 cnt[2]+cnt[4]+cnt[6]=3+2+1=6cnt[2] + cnt[4] + cnt[6] = 3 + 2 + 1 = 6,与样例一致。

越界与数值范围。 n=2×105n = 2 \times 10^5 且 ss 全是同一个字符时, occ(i)=n−i+1occ(i) = n - i + 1,答案 ≈n24=1010\approx \frac{n^2}{4} = 10^{10},超过 32 位整数, C++ 里必须用 long long(数据点 problem9.out 恰为 1000000000010000000000)。

代码

Python 版:

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++ 版(同一算法):

cpp
/**
 * 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 回跳总和为 O(n)O(n)(均摊分析:kk 每次循环至多 +1+1, 回跳总量不超过 +1+1 的次数),子树求和是一趟反向循环 O(n)O(n),累加答案 O(n)O(n), 总计 O(n)O(n)。实测最大数据点(n=200000n = 200000)C++ 约 0.01 s,Python 短解法同量级。
  • 空间:fail、cnt 各 O(n)O(n),字符串本身 O(n)O(n);合计 O(n)O(n)。 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 前缀函数的第二种典型用法。
  • 出现次数 = 子树大小:“PiP_i 出现”、“ii 是某个前缀的 border”、“该前缀长度对应的节点在 ii 的子树里” 三者等价,这个等价关系是本题唯一需要记住的观察。
  • 父亲的编号一定更小:因为真 border 严格更短,所以 i -> fail[i] 天然是"小指大"的 有向无环结构,子树求和退化成一行反向循环 cnt[fail[i]] += cnt[i], 不需要建树、不需要 DFS、不需要显式栈。
  • 注意答案上界:n=2×105n = 2 \times 10^5 时答案可达 101010^{10},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"]

观察重点有三个。第一,树是按编号递增分层的:fail[i]<ifail[i] < i,所以每条边都从小编号 指向大编号,这正是反向循环能当成"自底向上"用的原因。第二,根节点的三个儿子 是 a、ab、abababc——它们都是 fail 值为 00、不含非平凡 border 的前缀。 第三,答案只取偶数层:节点 2、4、6 的 cntcnt 是 3,2,13, 2, 1,和为 66; 若错误地把根节点 cnt=8cnt = 8 也算进去,答案就会偏大。