把 S 的全部前缀视为 trie 上的结点得集合 P,好串即 P·P;用 AC 自动机 fail 树的子树大小扣掉同一串的重复切分,答案从 |P|² 中扣除。
OJ: roj
题目 ID: 1709
难度:提高+/省选-
标签:字符串TrieAC自动机fail树python
创建: 2026-10-07 17:43
更新: 2026-10-07 17:43
形式化题目
给定
为「
求不同好串
关键改写。 条件只要求
要求的答案是集合
样例的表格化理解。 样例
a |
ab |
ac |
|
|---|---|---|---|
a |
aa |
aab |
aac |
ab |
aba |
abab |
abac |
ac |
aca |
acab |
acac |
九格两两不同,故答案为 aa、aab、aba、abab。四格互不相同,答案 problem3,其 .out 为 4,与公式 a×30 的退化情形
(随仓 problem9):
正解
思路
第一步:把
第二步:先写下界。
求和只遍历真正出现在
第三步:重复切分长什么样。 设同一串
又
合起来:较长的首段是较短首段后面接上块
第四步:把平移块归到结点上。 取 trie 上任意一个「有属于
这里的
第五步:数出到底多算了多少。 在 fail 树上,
把这两件事拼起来:对每个
这个扣除在数什么。 取某个满足
至少有两种切分:
注意这只证明了「每个
诚实说明。 上面只证明了「每个
对都能造出一个多余切分」这一方向; 而「这些实例恰好不重不漏地覆盖 (1) 式中的 」这一计数恒等式, 完整证明较长(需要讨论 个切分点构成等差数列、每个额外切分点唯一对应一个 )。 本题采用实测代替:把 (2) 式与「枚举 后对每个 数切分数」的暴力在 、 、字母表 / / 上随机对拍 2 万余组,两边逐组完全相等;结论是 (2) 式正确。 同时该式与素材源 std.cpp的写法等价(它把向上跳步写成一个while (hu2)循环, 效果同为「向上走步」),而 std.cpp在随仓 10 组数据上逐点与.out相符。
样例 root → a、a → ab、
a → ac 的形状,ab 的后缀 b、结点 ac 的后缀 c
都不在 a 的 fail 也是根。
于是 (2) 式的每一项都被跳过,答案
随仓 problem3(root → a → ab,a 的 fail 是根(跳过)。
结点 ab 的真后缀只有 b(不在 .out 的 4 一致。✓
随仓 problem9(a×30)复核。 trie 退化成深度 30 的一条链,
结点依次是 a、aa、…、a×30,.out 的 59 一致。✓
这个例子最能说明公式的力度:
代码
C++ 版把 trie 结点聚合成 struct Node(含出边、父亲、深度、fail、子树大小),
BFS 求 fail 时对每条失配链暴力找可行边——链长不超过
/**
* 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 17:43
* update_at: 2026-10-07 17:43
*/
// 1709 寻找好串
// 一本通 · 高手训练篇 二、字符串算法
//
// 题意:给出字符串集合 S。若串 w 能切成两个非空段 a、b,且 a、b 都是 S 中
// 某个串的前缀,则称 w 是「好」的。求不同好串的个数。
//
// 做法:把所有 S 中的串插入 trie,每个非根结点恰好对应一个非空前缀串,
// 于是前缀集合 P 的大小就是结点数 cnt,好串全体恰为 { p + q | p, q ∈ P }。
// 先按 cnt² 记,再扣掉「同一个串被多种切分重复生成」的次数:两种切分
// 必然相差一段平移块 x(长首段 = 短首段 + x,短尾段 = x + 长尾段)。
// 对每个有非空真后缀的结点 u(fail[u] 不是根),fail[u] 就是那个真后缀,
// t = s_u 去掉尾部 fail[u] 后的前缀;把 t 当作严格后缀的 P 内串个数
// 正是 fail 树上 t 的子树大小减一,累加即为全部多余切分。
//
// 验证:与「枚举 P×P 去重」的暴力在 n ≤ 4、|s| ≤ 6 上随机对拍 2 万余组全一致;
// 随仓 10 组数据逐点相符。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 300005; // 结点上界:n · 30 + 1
const int SIGMA = 26;
// trie / AC 自动机的结点:一个结点就是一个前缀串,字段聚合成 struct 而不是平行数组
struct Node {
int ch[SIGMA]; // 出边(初始全 0 表示没有边)
int fa; // 父亲结点
int dep; // 深度 = 该结点代表的前缀串长度
int fail; // 失配指针
ll sub; // fail 树上的子树大小(含自身)
};
Node node[MAXN];
int n; // 字符串个数
int cnt; // 已建结点数(不含根,根编号 0)
int order[MAXN]; // 按深度递增的访问序
char buf[64];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%s", buf + 1);
int len = (int)strlen(buf + 1), u = 0;
for (int j = 1; j <= len; j++) {
int c = buf[j] - 'a';
if (!node[u].ch[c]) {
node[u].ch[c] = ++cnt; // 开点:这个新结点对应一个新前缀
node[cnt].fa = u;
node[cnt].dep = node[u].dep + 1;
}
u = node[u].ch[c];
}
}
// BFS 求 fail:沿失配链找可走的边,链长不超过串长 30,代价可忽略
int head = 0, tail = 0;
for (int c = 0; c < SIGMA; c++)
if (node[0].ch[c]) order[tail++] = node[0].ch[c];
while (head < tail) {
int u = order[head++];
for (int c = 0; c < SIGMA; c++) {
int v = node[u].ch[c];
if (!v) continue;
int f = node[u].fail;
while (f && !node[f].ch[c]) f = node[f].fail;
node[v].fail = node[f].ch[c];
order[tail++] = v;
}
}
// fail 树子树大小:fail 指向更浅的结点,倒着扫访问序累加即可
for (int i = 1; i <= cnt; i++) node[i].sub = 1;
for (int k = cnt - 1; k >= 0; k--) {
int u = order[k];
node[node[u].fail].sub += node[u].sub;
}
// 扣除重复切分:u 有非空真后缀(fail[u] != root)时,
// 从 u 向上走 dep[fail[u]] 步得到祖先 t(深度等于 |fail[u]|),
// sub[t] - 1 是以 t 为严格后缀的 P 内串个数,即该平移块带来的多余切分。
ll ans = (ll)cnt * cnt;
for (int u = 1; u <= cnt; u++) {
if (!node[u].fail) continue; // 没有真后缀则不会产生平移
int t = u, steps = node[node[u].fail].dep;
while (steps--) t = node[t].fa;
ans -= node[t].sub - 1;
}
printf("%lld\n", ans);
return 0;
}Python 短解法保持同阶算法,但换了两处实现:trie 用「字典列表」表示稀疏出边;
取出祖先时用一张
#!/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 17:43
# update_at: 2026-10-07 17:43
import sys
from collections import deque
LOG = 5 # 2^5 = 32 > 串长上界 30,够跳完任意深度
type Trie = list[dict[int, int]] # 出边表:第 u 个结点存 字符 -> 子结点编号
type Up = list[list[int]] # 倍增祖先表:up[k][u] 是 u 向上 2^k 步的祖先
def build_trie(words: list[bytes]) -> tuple[Trie, list[int], list[int]]:
"""把所有串插入 trie,返回(出边表, 父亲, 深度)。
trie 上每个非根结点恰好对应一个非空前缀串,于是结点数 cnt 就是集合 |P|。
"""
nxt: Trie = [{}]
fa: list[int] = [0]
dep: list[int] = [0] # 深度 = 该结点代表的前缀串长度
for word in words:
u = 0
for c in word:
v = nxt[u].get(c)
if v is None:
v = len(nxt)
nxt[u][c] = v
nxt.append({})
fa.append(u)
dep.append(dep[u] + 1)
u = v
return nxt, fa, dep
def build_fail(nxt: Trie) -> tuple[list[int], list[int]]:
"""BFS 求 AC 自动机的 fail 指针,同时返回按深度递增的访问序。
找 fail 时沿失配链跳一步看有没有对应字符的边;链长 ≤ 30,代价可忽略。
"""
cnt = len(nxt) - 1
fail = [0] * (cnt + 1)
order: list[int] = []
queue = deque(nxt[0].values())
while queue:
u = queue.popleft()
order.append(u)
for c, v in nxt[u].items():
f = fail[u]
while f and c not in nxt[f]:
f = fail[f]
fail[v] = nxt[f].get(c, 0)
queue.append(v)
return fail, order
def build_up(fa: list[int]) -> Up:
"""建倍增祖先表:up[k][u] 为 u 向上 2^k 步的祖先。"""
up: Up = [fa]
for _ in range(LOG):
prev = up[-1]
up.append([prev[x] for x in prev])
return up
def ancestor_at(up: Up, node: int, height: int) -> int:
"""从 node 向上走 height 步(height ≤ 30,按二进制位拆开跳)。"""
bit = 0
while height:
if height & 1:
node = up[bit][node]
height >>= 1
bit += 1
return node
def count_good(
cnt: int,
fail: list[int],
dep: list[int],
sub: list[int],
up: Up,
) -> int:
"""好串个数:先按 cnt² 记,再扣掉每个平移块带来的重复切分。
u 有非空真后缀(fail[u] 不是根)时,平移块 t 是 u 向上 dep[fail[u]] 步的祖先;
sub[t] - 1 即以 t 为严格后缀的 P 内串个数,也就是这一块多算的次数。
"""
ans = cnt * cnt
for u in range(1, cnt + 1):
if not fail[u]:
continue
t = ancestor_at(up, u, dep[fail[u]])
ans -= sub[t] - 1
return ans
def solve() -> None:
data = iter(sys.stdin.buffer.read().split())
n = int(next(data))
words = [next(data) for _ in range(n)]
nxt, fa, dep = build_trie(words)
cnt = len(nxt) - 1
# fail 树子树大小:fail 指向更浅的结点,按访问序倒着累加即可
fail, order = build_fail(nxt)
sub = [1] * (cnt + 1)
for u in reversed(order):
sub[fail[u]] += sub[u]
print(count_good(cnt, fail, dep, sub, build_up(fa)))
if __name__ == "__main__":
solve()复杂度
记
- 插入:
。 - 求 fail:每个结点沿失配链上跳,单次不超过
,总计 ; 也常写成 的均摊上界,两者在本题取值下都远小于时限。 - fail 树子树统计:按访问序倒扫一次,
。 - 扣除阶段:每个结点一次向上跳
(Python 版为 ),共 。 - 综上,时间
。 - 空间:
( struct Node里出边数组个 int), Python 版额外维护的倍增表。
答案量级:int 天然支持)。
总结
- 核心转化:好串集合
,问题从「判定某个串好不好」变成 「数拼接结果里有多少个互不相同的串」。 - 容斥起点:
是二元组数,也就是答案的上界; 差额只由同一个串的多种切分产生。 - 重复的结构:两种切分必然相差一段平移块
, 即长首段 短首段 、短尾段 长尾段。 - fail 树的角色:
标记出「 有属于 的真后缀」, 块 由 去掉该后缀得到; 恰是以 为严格后缀的 内串数, 也就是该平移块带来的多余切分。 - 本题的实现坑:向上跳的步数是
而不是 ; 最早写错正是这一处,靠随仓数据逐点比对才发现。 - 题目来源为一本通《高手训练篇》字符串算法一节,属 AC 自动机 fail 树的计数型应用; 与「查询词命中计数」类问题(如 1479 Keywords Search)相比,本题把 fail 树当作 子树求和的计数工具,而不是命中标记的传播管道。
图示解析
下面用两条链式 trie 展示 fail 树上的扣除是怎么发生的,对应随仓 problem9
(a×30,答案
flowchart TD
R["root"] --> A1["a"]
A1 --> A2["aa"]
A2 --> A3["..."]
A3 --> A30["a×30"]
trie 是深度 sub[a] = 30 表示「30 个结点串都以 a 为后缀」:
flowchart LR
RF["root"] --> FA1["a"]
FA1 --> FA2["aa"]
FA2 --> FA3["aaa"]
FA3 --> FD["..."]
FD --> FA30["a×30"]
每个
数据来源说明。 素材源目录含
data.py(自造数据的分层生成脚本)与config.json, 说明随仓data/的 10 个测试点是重新生成的,而非官方评测数据;题面亦属网络资料重建。 因此「随仓数据通过」只证明解在本题面模型下自洽,不等于官方 AC。 分层设计覆盖了这些边界:problem1/2是的两个极端(单字符与纯链), problem3是重串与嵌套前缀,problem7/8是、 的顶格 (分别用 26 字母与 2 字母,后者 fail 链更深), problem9是个同一串的退化, problem10混入周期串与重复串对抗前缀/后缀重叠。