「一本通 2.4 练习 3」单词

形式化题目

给定 $N$ 个仅由小写字母组成的非空字符串 $S_1, S_2, \dots, S_N$ 。

定义这篇“论文”由这 $N$ 个字符串共同组成，要求对每个 $1 \leqslant i \leqslant N$ ，计算模式串 $S_i$ 作为子串在全体字符串中出现的总次数：

\text{ans}_i = \sum_{j=1}^N \text{count}(S_j, S_i)

其中 $\text{count}(T, P)$ 表示子串 $P$ 在文本串 $T$ 中的出现次数。

正解

思路

一个子串 $S_i$ 出现在文本中，等价于 $S_i$ 是该文本某个前缀的后缀。多模式串匹配的核心工具是 AC 自动机（Aho-Corasick Automaton）。

1. 朴素跳 fail 链的瓶颈

如果将所有模式串拼接后在 AC 自动机上匹配，并在每个前缀位置暴力沿着 fail 指针向上追溯所有匹配成功的模式串，在最坏情况（例如所有串都是相同字符构成的重复串 a, aa, aaa…）下，单次前缀可能需要回溯 $O(\sum |S_i|)$ 步，总时间复杂度将退化至 $O((\sum |S_i|)^2)$ ，导致超时。

2. fail 树与拓扑聚合优化

若将 AC 自动机中所有节点的 fail 指向视作有向边 $u \to \text{fail}[u]$ ，这些边构成了一棵以根节点（节点 0）为根的树，称为 fail 树。

在 fail 树中：

节点 $u$ 是节点 $v$ 的祖先，当且仅当节点 $u$ 所代表的字符串是节点 $v$ 所代表字符串的后缀。
如果我们在 Trie 树上统计每个节点被所有串的前缀经过的次数 $\text{cnt}[v]$ ，那么一个模式串 $S_i$ （对应节点 $pos_i$ ）的总出现次数，恰好等于 fail 树上以 $pos_i$ 为根的整棵子树中所有节点的初始权值之和。

graph TD
    subgraph Trie 树前缀匹配路径
        R[0: 根] --> A["1: 'a' (cnt=3)"]
        A --> AA["2: 'aa' (cnt=2)"]
        AA --> AAA["3: 'aaa' (cnt=1)"]
    end
    subgraph fail 树拓扑汇聚方向
        F3["3: 'aaa' (cnt=1)"] -->|"fail 指向"| F2["2: 'aa' (cnt=2+1=3)"]
        F2 -->|"fail 指向"| F1["1: 'a' (cnt=3+3=6)"]
    end

由于 fail 指针总是从深度大的节点指向深度较小的节点，BFS 构建 AC 自动机时节点出队的先后顺序天然构成了 fail 树的一个拓扑序。

因此，我们无需显式建立 fail 树反向边做树形 DFS，直接按 BFS 出队顺序的逆序（自底向上）执行状态转移：

\text{cnt}[\text{fail}[u]] \gets \text{cnt}[\text{fail}[u]] + \text{cnt}[u]

遍历完成后， $\text{cnt}[pos_i]$ 即为第 $i$ 个单词的总出现次数。

代码

Python 版：

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
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#!/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-09-30 14:00
# update_at: 2026-09-30 14:04

import sys
from collections import deque


def build_ac(words: list[str]) -> tuple[list[int], list[int], list[int]]:
    """构建 AC 自动机并返回 (各前缀经过计数, 各模式串对应节点, 广搜拓扑序)。"""
    trie: list[dict[str, int]] = [{}]
    cnt: list[int] = [0]
    pos: list[int] = []

    for w in words:
        u = 0
        for ch in w:
            if ch not in trie[u]:
                trie[u][ch] = len(trie)
                trie.append({})
                cnt.append(0)
            u = trie[u][ch]
            cnt[u] += 1  # 记录所有模式串前缀在该节点的覆盖次数
        pos.append(u)

    fail = [0] * len(trie)
    q = deque(trie[0].values())
    order: list[int] = []

    while q:
        u = q.popleft()
        order.append(u)
        for ch, v in trie[u].items():
            f = fail[u]
            while f and ch not in trie[f]:
                f = fail[f]
            fail[v] = trie[f][ch] if ch in trie[f] else 0
            q.append(v)

    return cnt, fail, order, pos


def count_occurrences(cnt: list[int], fail: list[int], order: list[int], pos: list[int]) -> list[int]:
    """按 fail 树自底向上聚合子树计数，返回每个模式串在所有串中的总出现次数。"""
    for u in reversed(order):
        cnt[fail[u]] += cnt[u]
    return [cnt[p] for p in pos]


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    words = [next(data).decode() for _ in range(n)]

    cnt, fail, order, pos = build_ac(words)
    ans = count_occurrences(cnt, fail, order, pos)
    print('\n'.join(map(str, ans)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
83
84
85/**
 * 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-05 03:45
 * update_at: 2026-10-05 03:45
 */
// AC 自动机 + fail 树子树聚合统计多模式串出现次数。
#include <cstdio>
#include <cstring>
#include <string>

typedef long long ll;

const int MAXNODE = 1000005; // 节点数不超过所有单词长度和 + 1
const int SIGMA = 26;

int ch[MAXNODE][SIGMA]; // Trie 转移：ch[u][c] = 节点 u 沿字符 c 的儿子
int fail[MAXNODE];      // fail 指针，构成以根为祖先的 fail 树
ll cnt[MAXNODE];        // cnt[u] = 所有模式串的前缀经过节点 u 的次数（后为子树聚合值）
int pos[205];           // pos[i] = 第 i 个单词在 Trie 上对应的终止节点
int order[MAXNODE];     // BFS 出队顺序，天然是 fail 树的拓扑序（父先于子）
int total_node = 1;     // 节点总数，0 号为根，1 号预留给第一个新建节点

// 把所有单词插进 Trie，并在每个经过的节点上累计前缀覆盖次数
void insert_word(const std::string &s, int idx) {
    int u = 0;
    for (unsigned int i = 0; i < s.size(); ++i) {
        int c = s[i] - 'a';
        if (ch[u][c] == 0) {
            ch[u][c] = total_node++;
        }
        u = ch[u][c];
        cnt[u]++; // 这个前缀被该模式串经过了一次
    }
    pos[idx] = u;
}

// BFS 建 fail 指针，同时记录出队顺序
void build_fail() {
    static int q[MAXNODE];
    int head = 0, tail = 0;
    for (int c = 0; c < SIGMA; ++c) {
        if (ch[0][c] != 0) {
            fail[ch[0][c]] = 0;
            q[tail++] = ch[0][c];
        }
    }
    while (head < tail) {
        int u = q[head++];
        order[head - 1] = u; // 出队顺序即拓扑序
        for (int c = 0; c < SIGMA; ++c) {
            int v = ch[u][c];
            if (v != 0) {
                fail[v] = ch[fail[u]][c];
                q[tail++] = v;
            } else {
                ch[u][c] = ch[fail[u]][c]; // 路径压缩成转移自动机
            }
        }
    }
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) return 0;
    for (int i = 0; i < n; ++i) {
        static char word[2000005]; // 单个单词最长可达总长度 10^6，用静态区避免爆栈
        scanf("%s", word);
        insert_word(word, i);
    }
    build_fail();

    // 按拓扑序的逆序（深度大到深度小）自底向上聚合 fail 树子树权值：
    // 节点 u 的所有出现都会贡献给它的后缀 fail[u]
    for (int i = total_node - 2; i >= 0; --i) {
        int u = order[i];
        cnt[fail[u]] += cnt[u];
    }

    for (int i = 0; i < n; ++i) {
        printf("%lld\n", cnt[pos[i]]);
    }
    return 0;
}

复杂度

时间复杂度： $O(\sum |S_i|)$ 。建立 Trie 树、广搜构建 fail 指针以及逆序拓扑累加权值均对每个节点处理常数次，总运行时间与所有单词的总长度之和呈严格线性关系。
空间复杂度： $O(\sum |S_i|)$ 。Trie 树的节点数量不超过 $\sum |S_i| + 1$ ，每个节点维护转移指针和整型计数变量，空间开销为线性阶。

总结

本题是 AC 自动机上经典利用 fail 树子树聚合 优化多模式串统计的范例。通过将前缀覆盖标记直接记录在 Trie 节点上，并沿 fail 树的拓扑逆序自底向上求和，彻底避免了暴力跳 fail 链的二次退化，实现了线性的时空复杂度。