[NOI2014] 动物园

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

KMP 统计 border 链长度，再用第二遍线性扫描限制前后缀不能重叠。

启发题

启发记录： 高难度题：border 链深与滑动 j 两个独立想法缺一不可，j 的线性靠能量账本（势能法）论证，代表'状态机+不变量'类算法的思考方式。

OJ: luogu

题目 ID: P2375

难度:提高+/省选-

标签:KMPborder计数势能法python

日期: 2026-07-16 19:57

前置题目

luogu P3435[POI 2006] OKR-Periods of Words失配链递推的深度进阶：从求最短 border 到统计链上长度不超过一半的节点数

题意

对每个前缀，统计同时是前缀和后缀且两份不重叠的非空字符串数量 num[i]，求所有 num[i]+1 的乘积。

思路

解法的演进分三步，下面的小节按这三步展开：代码1先用 KMP 的 pi 链暴力数；代码2用链深 border_count 让"数"变成 $O(1)$ ；代码3用滑动 j 让"找"也变成线性。三个想法相互独立、缺一不可。

代码1：沿 pi 链暴力数

先固定术语：border = 既是真前缀又是真后缀的非空字符串；前缀函数 pi[i] = s[0..i] 的最长 border 长度（即 KMP 的失配跳转表，下标从 0 开始，与 rbook 文章一致）。

难点在"全部"两个字：pi[i] 只回答最长的那个。但 border 有嵌套结构——aa 的 border 是 a，aaa 的 border 是 aa……每个 border 的 border 还是 border。所以沿 pi 一路回退（在失配树上向父节点跳跃），就能走遍前缀的全部 border。以 abcababc 的失配树为例（每个节点是一个前缀，节点编号 i 对应前缀 s[0..i]，父节点就是 pi[i]-1）：

text

1
2
3
4
5
6
7
8
9
10
11                                  ┌──────────┐
                                  │空串（根）│
                                  └──────────┘
           ┬────────────────────────────┴──┬────────────────────────┬
        ┌─────┐                        ┌──────┐                 ┌───────┐
        │a (0)│                        │ab (1)│                 │abc (2)│
        └─────┘                        └──────┘                 └───────┘
     ┬─────┴────────┬              ┬───────┴───────┬                 │
┌────────┐    ┌──────────┐    ┌─────────┐    ┌───────────┐    ┌────────────┐
│abca (3)│    │abcaba (5)│    │abcab (4)│    │abcabab (6)│    │abcababc (7)│
└────────┘    └──────────┘    └─────────┘    └───────────┘    └────────────┘

图中 ─┴─ 是父节点向下的连线，─┬─ 是连到子节点的分叉。第三层从左到右：3、5 挂在 a 下，4、6 挂在 ab 下，7 挂在 abc 下。

任意前缀的 border 链 = 它到根的整条路径：节点 7（abcababc）走 7 -> 2 -> 根，border 只有 abc；节点 4（abcab）走 4 -> 1 -> 根，border 是 ab。

所以：拿到 pi 就等于拿到了所有 border 的组织方式，“数 border 的个数"本质是"数到根路径上的节点数”。最直接的写法（代码1）就是：对每个前缀 i，沿 pi 链一步步跳到 0，边跳边数"长度 ≤ i/2 的节点"。它正确，但全 a 串里每条链都有 $O(L)$ 个节点，总复杂度退化成 $O(L^2)$ 。下面两步分别解决"数"和"找"的浪费。

代码2：border_count 把"数"变成 O(1)

先看浪费在哪里：代码1 每走到一个节点都要停下来判断"是否 ≤ i/2"，但失配树是固定的，可以一次扫描把刻度刻好：

text

1border_count[i] = border_count[pi[i] - 1] + 1   （pi[i] = 0 时为 1）

它表示节点 i 到根经过几个节点（例：aaaaa 的 border_count = [1,2,3,4,5]）。之后"链上有几个节点"就变成查表 $O(1)$ 。

再看 abcababc：pi = [0,0,0,1,2,1,2,3] → border_count = [1,1,1,2,2,2,2,2]。以节点 7 为例：pi[7] = 3，所以 border_count[7] = border_count[2] + 1 = 2——它的链是 7 -> 2 -> 根 共 2 个节点（7 自己 + abc）。注意 border_count[7] 和 num[7] 不是一回事：num[7] 数的是 7 的祖先（不含 7 自己），由代码3小节的公式给出 num[7] = border_count[j-1] = border_count[2] = 1。

两个容易卡住的细节：

pi[i] = 0（没有 border）时 border_count[i] = 1 而不是 0：border_count 数的是"从节点 i 出发沿链走到根、含 i 自己"的节点数，不是"前缀 i 自己的 border 数"。i 自己在链上必须算——当更长的前缀把 i 当作 border 时，它就是一个真实存在的 border（例：aa 的 border a 是节点 0，border_count[0] = 1 正好算 1 个）。而"前缀 i 没有 border"（num = 0）的情况由游标 j == 0 的分支处理，根本不会去读 border_count[j-1]，所以这里 1 还是 0 不影响答案。
为什么链上要包含 i 自己，再看一个完整例子：前缀 aaaa（0 下标 i=3）的 num = 2，border 是 a 和 aa 两个；它的最长不重叠 border 是 aa（j=2，节点 1），border_count[1] = 2 正好数出这两个——链顶 aa 自己就是 aaaa 的合法 border（真前缀/真后缀，不是整个串），必须算。所以 border_count[x] 的正确理解是"从 x 出发沿链跳，能数到几个 border 候选"，x 自己永远是第一个候选。

所以：数量问题解决。但代码2 每个前缀仍然要沿链走，先找到"第一个合法节点 j"再用查表——最坏还是 $O(L^2)$ 。这就是分水岭：border_count 解决"数得快"，接下来代码3 解决"找得快"，两个想法相互独立、缺一不可。

代码3：滑动 j 把"找"也变成线性

"数到哪一点"由不重叠决定：border 长度不能超过前缀长度的一半。记 j = 链上最长的合法 border，则 num[i] = border_count[j-1]（这就是代码2 里 num[7] = 1 的来历）。

j 不必每个前缀重新找：i 每次只长 1，上一轮的 j 就是本轮最好的起点。每轮只可能有三种情况，对应代码里的三个 while：

接得上：s[i] == s[j] → j++，border 延长 1；
失配：s[i] != s[j] → 长度 j 的 border 延长不了，但更短的还可能——所有比 j 短的 border 正是失配树上 j 的祖先（j -> pi[j-1] -> ...），所以回退一步再比较，仍失配就继续回退，直到匹配或 j 归零（与构造 pi 时的失配处理完全相同）；
重叠：接上之后 2*j > 前缀长度 → 继续沿链回退，直到不重叠。

这样不会漏掉候选：新前缀的任何 border 都只能由旧前缀的某个 border 接上新字符得到（见本节下面的证明），而旧前缀不超过 j 的所有 border 正好就是这条祖先链，逐个检验能否延长即可。

以 aaaaa 演示（0 下标，pi = [0,1,2,3,4]，border_count = [1,2,3,4,5]）：

i	j 尝试	结果	最终 j	num[i]
1	接上 → 1	2*1 = 2 ≤ 2 ✓	1	`border_count[0]` = 1
2	接上 → 2	2*2 = 4 > 3，回退 j = pi[1] = 1	1	`border_count[0]` = 1
3	接上 → 2	2*2 = 4 ≤ 4 ✓	2	`border_count[1]` = 2
4	接上 → 3	2*3 = 6 > 5，回退 j = pi[2] = 2	2	`border_count[1]` = 2

看第 3 行（前缀 aaaa，i=3）：border 是 a、aa、aaa，不重叠的只有前两个；j 停在 2，border_count[1]=2 直接给出个数。第 4 行演示"重叠就回退"：j 试到 3，但 2*3 > 5，沿链退到 2。每行的因子是 num[i]+1，把它们乘起来并对 $10^9+7$ 取模。

为什么 j 每轮至多 +1（这是"滑动"正确的根基，也解释了上面"不漏掉候选"的论断）：前缀 i+1 的任意长度 L 的 border，去掉最后一个字符，得到长度 L-1 的串，它恰好是前缀 i 的一个 border——前缀部分没变，后缀部分整体左移一位即可对齐。因此若新前缀的最长 border 能达到 L > j+1，则 L-1 > j 也是旧前缀 i 的 border，与"j 是最长"矛盾。"不重叠"限制不破坏这个性质：合法的 j 去掉末字符后仍满足 2(L-1) <= i-1，还是旧前缀的合法候选，故 j_i <= j_{i-1} + 1 依然成立。

所以：j 的增大每轮至多 1，回退只减不增——这正是复杂度节"能量账本"论证的前提，整个第二遍扫描是线性的 $O(L)$ 。

读代码时的小换算

叙述一直用"前缀长度"说话，代码从 0 开始，换算只有三处：

pi[i] ↔ 长度 i+1 的前缀的最长 border 长度；
游标 j ↔ 长度 j 的 border，下一个要比较的字符是 s[j]；
重叠判断 2*j <= i+1 ↔ border 长度不超过前缀长度的一半。

Python 知识

sys.stdin.buffer.readline 逐测试串读取，不会同时保留最多五个百万字符数组。
array("i") 控制 prefix 和计数数组的内存。
Python 整数乘法后立即 % MOD，无需考虑溢出。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37import sys
from array import array


MOD = 10**9 + 7
input = sys.stdin.buffer.readline
answers = []

for _ in range(int(input())):
    word = input().strip()
    n = len(word)
    prefix = array("i", [0]) * (n + 1)
    border_count = array("i", [0]) * (n + 1)
    border_count[1] = 1

    for length in range(2, n + 1):
        j = prefix[length - 1]
        while j and word[length - 1] != word[j]:
            j = prefix[j]
        if word[length - 1] == word[j]:
            j += 1
        prefix[length] = j
        border_count[length] = border_count[j] + 1

    answer = 1
    j = 0
    for length in range(2, n + 1):
        while j and word[length - 1] != word[j]:
            j = prefix[j]
        if word[length - 1] == word[j]:
            j += 1
        while j * 2 > length:
            j = prefix[j]
        answer = answer * (border_count[j] + 1) % MOD
    answers.append(str(answer))

print("\n".join(answers))

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82/**
 * 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-08-02
 * update_at: 2026-08-02
 */

/* P2375 [NOI2014] 动物园 */
/* 核心观察：
 *   1. 前缀的所有 border 按长度严格嵌套成一条链（失配树上的一条祖先路径）。
 *   2. num[i] = 链上长度不超过 (i+1)/2 的节点个数。
 *   3. 链深一次扫描刻好刻度；游标 j 每轮至多 +1，第二遍扫描线性。 */
/* 下标约定与 rbook 文章《KMP 字符串匹配》一致：从 0 开始。 */

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000000 + 7;

// 前缀函数模板（原样取自 rbook 文章《KMP 字符串匹配》）
// pi[i]：pattern[0..i] 的最长相等真前后缀长度，pi[0] = 0
vector<int> build_prefix_function(const string &pattern) {
    int m = (int)pattern.size();
    vector<int> pi(m, 0);

    for (int i = 1; i < m; i++) {
        int j = pi[i - 1];                 // 上一个位置的最长 border
        while (j > 0 && pattern[i] != pattern[j]) {
            j = pi[j - 1];                 // 失配：在失配树上向父节点跳跃
        }
        if (pattern[i] == pattern[j]) j++; // 匹配成功，border 延长 1
        pi[i] = j;
    }

    return pi;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; // 测试数据组数
    cin >> n;
    while (n--) {
        string s;
        cin >> s;
        int L = (int)s.size();

        /* 第一遍：前缀函数 pi */
        vector<int> pi = build_prefix_function(s);

        /* 刻度：border_count[i] = 失配树上节点 i 到根的节点数（含自己） */
        // 例：s = aaaaa → pi = [0,1,2,3,4]，border_count = [1,2,3,4,5]
        vector<int> border_count(L, 0);
        for (int i = 0; i < L; i++) {
            if (pi[i] > 0)
                border_count[i] = border_count[pi[i] - 1] + 1; // 父节点下标是 pi[i]-1
            else
                border_count[i] = 1; // 没有 border，链上只有自己
        }

        /* 第二遍：游标 j 扫描，求 num[i] */
        // j 沿用文章含义"已匹配前缀长度"，下一个要比较的字符是 s[j]；
        // 额外要求 2*j <= i+1（不重叠）。
        long long ans = 1; // 答案：所有 (num[i]+1) 的乘积；num[0] 恒为 0，从 i=1 开始
        int j = 0;
        for (int i = 1; i < L; i++) {
            while (j > 0 && s[i] != s[j]) j = pi[j - 1]; // 失配回退
            if (s[i] == s[j]) j++;                        // 匹配，j 延长 1
            while (j * 2 > i + 1) j = pi[j - 1];          // 重叠，继续沿链缩短

            // num[i] = border_count[j-1]；j == 0 时没有 border，因子是 1
            int factor = (j == 0) ? 1 : border_count[j - 1] + 1;
            ans = ans * factor % MOD;
        }

        cout << ans << '\n';
    }

    return 0;
}

复杂度

先给一个能量账本式的均摊论证，两遍扫描都靠它（这也是 KMP 一族——构造 pi、KMP 匹配、AC 自动机——共用的论证）。

设游标 j 从 0 开始处理 $n$ 轮，只需两个事实：

增加次数 ≤ n：每轮至多 +1（见思路代码3小节的证明），所以总增加 $Inc \le n$ ；
减少次数 ≤ 增加次数：每次回退 j = pi[j-1] 至少减 1，且 $j \ge 0$ 恒成立——j 从 0 出发、回退到 0 就停，所以"总的减"不可能超过"总的加"：

0 + Inc - Dec \ge 0 \quad \Rightarrow \quad Dec \le Inc

于是总操作数 $= Inc + Dec \le 2n = O(n)$ 。

这就是势能法/均摊分析：把 +1 看作充能、回退看作放电，能量守恒保证线性。它不依赖字符长什么样——任何满足"至多 +1、只减不增、下界 0"的游标都是 $O(n)$ ，这也是它能自然推广到 AC 自动机、双指针等算法的原因。

第一遍（构造 pi）：套用能量账本论证， $O(L)$ 。

刻度递推（border_count）：一次 $O(L)$ 循环。

第二遍（游标 j）：同样套用能量账本论证——失配回退和重叠回退都是"减少"，只减不增， $O(L)$ 。

空间：pi、border_count 两个数组各 $O(L)$ 。

每组测试总时间 $O(|S|)$ 、空间 $O(|S|)$ 。

难点在哪

这题难在"想"而不是"写"：代码只有三个 while，但其中的 j 是本题自己发明出来的状态机。

border_count 的发现：把"数全部 border"转成"失配树上的链深"，本质是一个小 DP（border_count[i] = border_count[pi[i]-1] + 1）。卡点在于从"pi 只给最长"想到"全部 border 是一条链"——没有这一步，后面全部无从谈起。
j 的线性推进：第二遍扫描要求"每步结束时 j 等于当前前缀的最长不重叠 border"。这个性质不是 a→b→c 的因果链，而是一个不变量；它的正确性论证（每步至多 +1、回退只减）与构造 pi 时 j 的论证完全同构，只是多了一条"重叠就回退"的规则。所以真正难的其实是 KMP 本身就有的难点：j 凭什么能跟着 i 线性走——本题只是把它搬到了新场景。
人怎么验证这样的算法：不变量必须在"多个数据点"上分别验证，因为一个样例只能暴露一个分支——全 a 串暴露链深与重叠回退（aaaaa 的 i=3）、abcababc 暴露失配回退（i=5 处 j 从 2 退到 0 再重匹配）、ab 暴露 j=0 无 border 分支。一个样例永远"骗不过"自己，这正是"极限思维 + 对拍"存在的意义：挑极端数据把每个分支逼出来。

启示：遇到"状态机 + 不变量"类的算法（KMP、AC 自动机、双指针均摊），学的不是代码，而是两件事——找到那个不变量，以及构造一组覆盖所有分支的极端样例。

总结

本题的关键有三层：把"数量"转成 border 链长度；让非重叠限制通过 2*j <= length 落到同一条链上；以及让游标 j 线性推进的根基——i 每走一步，border 至多延长 1，所以 j 不必从头找，继承上一轮常数时间即可。

P2375 [NOI2014] 动物园

题目描述

近日，园长发现动物园中好吃懒做的动物越来越多了。例如企鹅，只会卖萌向游客要吃的。为了整治动物园的不良风气，让动物们凭自己的真才实学向游客要吃的，园长决定开设算法班，让动物们学习算法。

某天，园长给动物们讲解 KMP 算法。

园长：“对于一个字符串 $S$ ，它的长度为 $L$ 。我们可以在 $O(L)$ 的时间内，求出一个名为 $\mathrm{next}$ 的数组。有谁预习了 $\mathrm{next}$ 数组的含义吗？”

熊猫：“对于字符串 $S$ 的前 $i$ 个字符构成的子串，既是它的后缀又是它的前缀的字符串中（它本身除外），最长的长度记作 $\mathrm{next}[i]$ 。”

园长：“非常好！那你能举个例子吗？”

熊猫：“例 $S$ 为 $\verb!abcababc!$ ，则 $\mathrm{next}[5]=2$ 。因为 $S$ 的前 $5$ 个字符为 $\verb!abcab!$ ， $\verb!ab!$ 既是它的后缀又是它的前缀，并且找不到一个更长的字符串满足这个性质。同理，还可得出 $\mathrm{next}[1] = \mathrm{next}[2] = \mathrm{next}[3] = 0$ ， $\mathrm{next}[4] = \mathrm{next}[6] = 1$ ， $\mathrm{next}[7] = 2$ ， $\mathrm{next}[8] = 3$ 。”

园长表扬了认真预习的熊猫同学。随后，他详细讲解了如何在 $O(L)$ 的时间内求出 $\mathrm{next}$ 数组。

下课前，园长提出了一个问题：“KMP 算法只能求出 $\mathrm{next}$ 数组。我现在希望求出一个更强大 $\mathrm{num}$ 数组一一对于字符串 $S$ 的前 $i$ 个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作 $\mathrm{num}[i]$ 。例如 $S$ 为 $\verb!aaaaa!$ ，则 $\mathrm{num}[4] = 2$ 。这是因为 $S$ 的前 $4$ 个字符为 $\verb!aaaa!$ ，其中 $\verb!a!$ 和 $\verb!aa!$ 都满足性质‘既是后缀又是前缀’，同时保证这个后缀与这个前缀不重叠。而 $\verb!aaa!$ 虽然满足性质‘既是后缀又是前缀’，但遗憾的是这个后缀与这个前缀重叠了，所以不能计算在内。同理， $\mathrm{num}[1] = 0,\mathrm{num}[2] = \mathrm{num}[3] = 1,\mathrm{num}[5] = 2$ 。”

最后，园长给出了奖励条件，第一个做对的同学奖励巧克力一盒。听了这句话，睡了一节课的企鹅立刻就醒过来了！但企鹅并不会做这道题，于是向参观动物园的你寻求帮助。你能否帮助企鹅写一个程序求出 $\mathrm{num}$ 数组呢？

特别地，为了避免大量的输出，你不需要输出 $\mathrm{num}[i]$ 分别是多少，你只需要输出所有 $(\mathrm{num}[i]+1)$ 的乘积，对 $10^9 + 7$ 取模的结果即可。

输入格式

第 $1$ 行仅包含一个正整数 $n$ ，表示测试数据的组数。
随后 $n$ 行，每行描述一组测试数据。每组测试数据仅含有一个字符串 $S$ ， $S$ 的定义详见题目描述。数据保证 $S$ 中仅含小写字母。输入文件中不会包含多余的空行，行末不会存在多余的空格。

输出格式

包含 $n$ 行，每行描述一组测试数据的答案，答案的顺序应与输入数据的顺序保持一致。对于每组测试数据，仅需要输出一个整数，表示这组测试数据的答案对 $10^9+7$ 取模的结果。输出文件中不应包含多余的空行。

输入输出样例 #1

输入 #1

text

1
2
3
43
aaaaa
ab
abcababc

输出 #1

text

说明/提示

测试点编号	约定
1	$n \le 5, L \le 50$
2	$n \le 5, L \le 200$
3	$n \le 5, L \le 200$
4	$n \le 5, L \le 10,000$
5	$n \le 5, L \le 10,000$
6	$n \le 5, L \le 100,000$
7	$n \le 5, L \le 200,000$
8	$n \le 5, L \le 500,000$
9	$n \le 5, L \le 1,000,000$
10	$n \le 5, L \le 1,000,000$

[NOI2014] 动物园

目录

题意

思路

代码1：沿 pi 链暴力数

代码2：border_count 把"数"变成 O(1)

代码3：滑动 j 把"找"也变成线性

读代码时的小换算

Python 知识

代码

复杂度

难点在哪

总结