把 N 个模式串建成 Trie 并在每个结点记录结尾计数，每个询问沿路径走一遍累加经过结点的计数，O(总长度) 建树、每次询问 O(|T|) 回答。
OJ: roj
题目 ID: 3041
难度:普及
标签:Trie字典树字符串python
创建: 2026-10-01 11:39
更新: 2026-10-06 11:32
后置题目
roj 3042「The XOR Largest Pair」 最大异或对B 的 build_trie 逐位插入 01-Trie 时直接复用 A 教的「边存在就复用、不存在就新建儿子」这一建树步骤（代码里 nxt == NO_CHILD 才新建），把字符路径换成二进制位路径；A 原文也点明 01-Trie 建立在这套骨架上，B 另叠加 A 未教的高位优先相反位贪心。roj 2096usaco-6.1.3 奶牛异或B 的 01-Trie 直接复用 A 教的「按需建儿子、从根逐层下走」的 Trie 建树方式，只把字符边换成二进位边，再叠加反向位贪心与平局规则roj 1484「一本通 2.4 练习 5」病毒B 的 AC 自动机前半段直接复用 A 教的「从根逐字符下走、缺边新建儿子」的 Trie 建树骨架与根到节点路径即前缀的对应，只是把 A 的共享前缀计数结点升级成安全前缀等价类，再叠加 fail 指针、危险标记传播与安全子图 Kahn 判环。roj 1479「一本通 2.4 例 1」Keywords SearchB 的 build_automaton 直接复用 A 教的 Trie 建树骨架——从根逐字符下走、缺边新建儿子，并把计数挂在结尾结点（cnt[node] += 1，使「重复查询词各算一次」）；A 的原文也点明后续 AC 自动机建立在这套骨架上，B 只是在此之上叠加 A 未教的 fail 指针、BFS 求 fail 与 fail 树逆序传播命中。roj 1476「一本通 2.3 练习 3」Secret Message 秘密信息B 的第 1 类统计就是照搬 A 教的「沿查询路径累加结尾计数」，只在其上补了终点 through-end 来处理反向（信息比密码长）的前缀情形roj 1473「一本通 2.3 例 3」Nikitosh 和异或B 的 01-Trie 直接把 A 教的「从根下走、边不存在就新建儿子」建树骨架搬到位串上（main.cpp 的 trie_insert：nxt==0 就 ++top_node 挂边），再叠加 A 未教的反向位贪心查询与分割点拆分。roj 1472「一本通 2.3 例 2」The XOR Largest PairB 的 01 字典树建树（main.py 的 insert）直接复用 A 教的 Trie 插入骨架——逐层从根下走、边存在就复用、缺边就新建儿子，只是把字符换成二进制位；在此之上 B 才叠加 A 未教的高位优先贪心（每层优先走反向边）求最大异或对。luogu P17416「IXOI R3」我才不玩原神呢B 的查询过程复用了 A 教的「从根沿 Trie 逐字符（此处换成二进制位）下走」的遍历骨架，只是把路径累加计数换成按位贪心选相反分支、取前 k-1 大异或和的新流程。luogu P3808AC 自动机（简单版）B 的 AC 自动机第一步直接复用 A 教的 Trie 插入与「终止结点累计结尾个数」：P3808 main.cpp 的 insert_pattern 与 end_count[u]++ 和 A 的 insert/cnt[结点] 完全同构，A 停在用路径累计计数回答前缀询问，B 在此之上再叠加 fail 指针与文本串扫描的 fail 链统计。
题目描述
给定
思路
把所有模式串插入 Trie，每个结点记录在此结尾的串数；询问时沿
参考代码
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-01 11:39
# update_at: 2026-10-01 11:39
import sys
children: list[dict[int, int]] = [{}] # children[i][字符编码] = 结点 i 沿该边的儿子编号
cnt: list[int] = [0] # cnt[i] = 在结点 i 结尾的 S_i 个数（即它作为完整串出现几次）
def insert(word: bytes) -> None:
"""把 word 插进 Trie：已有的边直接走，缺的边现建儿子。"""
node = 0
for ch in word:
nxt = children[node].get(ch)
if nxt is None:
nxt = len(children)
children.append({})
cnt.append(0)
children[node][ch] = nxt
node = nxt
cnt[node] += 1
def count_prefix(word: bytes) -> int:
"""word 是多少个 S_i 的前缀：word 的每个前缀对应 Trie 根向下的一条路径，累加路径各点的结尾计数。"""
node, total = 0, 0
for ch in word:
node = children[node].get(ch, -1)
if node < 0: # 这条前缀在 Trie 里都走不出来，更长的更不可能
break
total += cnt[node]
return total
def solve() -> None:
data = iter(sys.stdin.buffer.read().split()) # 保留 bytes：顺序消费时逐个产出字符编码，省去解码
n, m = int(next(data)), int(next(data)) # 第一行的 N、M
for _ in range(n):
insert(next(data))
print('\n'.join(str(count_prefix(next(data))) for _ in range(m)))
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-06 11:32
* update_at: 2026-10-06 11:32
*/
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
const int MAXN = 1000005; // 总长度不超过 1e6，结点数最多为总长 + 1
int trie[MAXN][26]; // trie[u][c] 表示结点 u 沿字符 c 的下一个结点编号
int cnt[MAXN]; // cnt[u] 表示以结点 u 结尾的字符串个数
int node_cnt; // 当前 Trie 结点总数，结点 0 为根
// 把字符串 s 插入 Trie，并在结尾结点累加计数
void insert(const string &s) {
int u = 0;
for (size_t i = 0; i < s.size(); i++) {
int c = s[i] - 'a';
if (trie[u][c] == 0) {
trie[u][c] = ++node_cnt;
}
u = trie[u][c];
}
cnt[u]++;
}
// 查询有多少个模式串是 s 的前缀
int query(const string &s) {
int u = 0;
int ans = 0;
for (size_t i = 0; i < s.size(); i++) {
int c = s[i] - 'a';
if (trie[u][c] == 0) {
break; // 当前前缀不再是任何模式串的前缀，后续也不可能
}
u = trie[u][c];
ans += cnt[u];
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) {
return 0;
}
string s;
for (int i = 1; i <= n; i++) {
cin >> s;
insert(s);
}
for (int i = 1; i <= m; i++) {
cin >> s;
cout << query(s) << '\n';
}
return 0;
}