【例3-2】单词查找树

形式化题目

给定一个单词列表，每行一个单词，只含大写字母，单词长度不超过 63 个字母，文件总长度不超过 32K，至少有一行。

需要构造一棵单词查找树，满足：

根结点不含字母，除根结点外每个结点只包含一个大写英文字母；
从根结点到某个结点，路径上经过的字母依次连起来构成该结点对应的单词，单词列表中的每个单词都对应树上某个结点；
在满足上述条件下，该单词查找树的结点数最少。

求这棵单词查找树的结点数（包含根结点）。

样例：输入 A、AN、ASP、AS、ASC、ASCII、BAS、BASIC（每行一个单词），输出 13。

解法总览

两种解法建立在同一个观察上：每个非根结点恰好对应「某个输入单词的一个前缀」。只要公共前缀被共享、不重复开点，结点数就自动最少，于是答案 = 去重后的非空前缀个数 + 1（根结点），重复单词不影响答案。

解法	做法	时间	空间	代码
解法一（正式主解）	排序后每个单词只与前一单词比 LCP，直接累加新前缀数，不建树	$O(S \log n)$	$O(S)$	`main.py` / `main.cpp`
解法二	按单词列表建出字典树，再从根出发 DFS 遍历数结点	$O(S)$	$O(26S)$ 结点池	`trie_dfs.cpp` / `trie_dfs.py`

两者的差别只在「要不要真的把树建出来」：解法一省掉结点池，代价是多一次排序；解法二直接得到题面说的那棵树，还顺带得到整棵树的结构。正式主解是 main.py / main.cpp。

解法一：排序 + LCP 计数（免建树）

思路

结点数最少时，树上每个非根结点恰好对应"某个输入单词的一个前缀"，所以答案就是去重后的非空前缀个数加 1（根结点），重复单词不影响答案。把单词按字典序排序后，一个单词与前面所有单词的最长公共前缀（LCP）的最大值总在相邻位置取到，于是第 $i$ 个单词新贡献 $|w_i| - LCP(w_i, w_{i-1})$ 个结点，第一个单词贡献全部 $|w_1|$ 个前缀。因此答案 $= 1 + |w_1| + \sum_{i=2}^{n} (|w_i| - LCP(w_i, w_{i-1}))$ ，无需真正建树，复杂度为读入加排序的 $O(S \log n)$ （ $S \le 32\text{K}$ ）。

代码

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#!/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 05:57
# update_at: 2026-10-12 14:52

# 单词查找树的最少结点数 = 去重后的不同前缀个数（含根），
# 用「排序 + 相邻 LCP 计数」直接算出，不真正建树：
# 字典序排序后，第 i 个单词与前面所有单词 LCP 的最大值就是它与前一单词的 LCP，
# 于是它新贡献的结点数 = len(w) - LCP(w, 前一单词)，重复单词贡献 0。
# 如何使用：
# 1. read_words()   按空白切分读入单词表并整体排序（bytes，忽略空行）
# 2. common_prefix(a, b)  求最长公共前缀长度
# 3. count_nodes()  累加 1 + Σ(len(w) - 相邻 LCP)，1 是根结点
# 4. solve()        输出结点总数

import sys

words: list[bytes] = []  # 单词表：bytes 保存，逐字节比较最直接


def read_words() -> None:
    """按空白切分读入所有单词；每行一个，多余的空行自动忽略。"""
    global words
    words = sorted(sys.stdin.buffer.read().split())


def common_prefix(a: bytes, b: bytes) -> int:
    """a、b 的最长公共前缀长度：按位比较，遇到第一个不同的字母就停。"""
    i = 0
    while i < len(a) and i < len(b) and a[i] == b[i]:
        i += 1
    return i


def count_nodes() -> int:
    """结点数 = 1 + Σ(len(w_i) - LCP(w_i, w_{i-1}))，1 是根结点。"""
    nodes = 1 + len(words[0])  # 第一个单词贡献它的全部前缀
    for i in range(1, len(words)):
        # 与前一单词的 LCP 就是与前面所有单词 LCP 的最大值，重复单词贡献 0
        nodes += len(words[i]) - common_prefix(words[i], words[i - 1])
    return nodes


def solve() -> None:
    read_words()
    print(count_nodes())


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/**
 * 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 10:38
 * update_at: 2026-10-12 14:55
 */
// main.cpp：排序 + 相邻 LCP 计数求单词查找树结点数（不建树）。
//
// 最少结点数 = 去重后的不同前缀个数（含根）。字典序排序后，
// 第 i 个单词与前面所有单词 LCP 的最大值就是它与前一单词的 LCP，
// 所以它新贡献的结点数 = 长度 - 与前一单词的最长公共前缀，重复单词贡献 0。

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

typedef long long ll;

const int maxn = 20005; // 文件总长 32K，每个单词至少 1 字母 + 换行，单词数不超过 2 万

string word[maxn]; // 所有单词，读入后整体排序
ll cnt;            // 单词个数

// 读入全部单词：每行一个，按空白切分
void read_words() {
    while (cin >> word[cnt]) {
        cnt++;
    }
}

// a、b 的最长公共前缀长度：逐位比较，遇到第一个不同的字母就停
ll lcp(const string &a, const string &b) {
    ll la = a.size(); // 长度声明成 ll，就不用再做强制转换
    ll lb = b.size();
    ll i = 0;
    while (i < la && i < lb && a[i] == b[i]) {
        i++;
    }
    return i;
}

// 排序后统计结点数：1 + Σ(单词长度 - 与前一单词的 LCP)，1 是根结点
ll count_nodes() {
    sort(word, word + cnt);
    ll ans = 1 + word[0].size(); // 第一个单词贡献它的全部前缀
    for (ll i = 1; i < cnt; i++) {
        ll len = word[i].size();
        ans += len - lcp(word[i], word[i - 1]); // 重复单词 LCP 等于长度，贡献 0
    }
    return ans;
}

void solve() {
    read_words();
    cout << count_nodes() << endl;
}

int main() {
    solve();
    return 0;
}

复杂度

时间：读入 $O(S)$ ，排序 $O(S \log n)$ （字符串比较本身不超过单词长度），求 LCP 扫过全部字符 $O(S)$ ，合计 $O(S \log n)$ 。
空间： $O(S)$ ，用来存全部单词；不建树，没有结点池。

解法二：建立字典树 + 树上 DFS

思路

题面本身描述的就是「单词查找树」，这一解法按题面直译：先把树建出来，再在树上遍历统计结点数，对任意合法输入都成立。

第一步：建树（动态开点的字典树）。

新建一个不含字母的根结点。依次插入每个单词：从根出发，沿着当前字符往下走；对应的儿子已经存在就直接复用，不存在才开一个新结点，走到单词末尾为止。

公共前缀只保留一份，每个前缀最多对应一个结点，所以结点数自动最少；
重复单词走的是同一条已有路径，一个点也不会多开；
结点总数不超过文件总长度 32K，用静态结点池 + node_cnt 当分配指针即可，不需要指针或动态内存。

第二步：树上 DFS 统计结点数。

从根出发递归遍历，dfs(u) 返回以 $u$ 为根的子树有多少个结点（含 $u$ 自己）：

text

1dfs(u) = 1 + Σ dfs(儿子)，只累加实际存在的儿子

每条存在的边恰好被走一次、每个结点恰好被访问一次，所以 dfs(根) 就是整棵树的结点数。递归深度不超过单词长度 63，不会爆栈。

代码

C++ 版（静态结点池 + next[26] 数组）：

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/**
 * 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-11 22:18
 * update_at: 2026-10-11 22:18
 */
/*
 * trie_dfs.cpp：【例3-2】单词查找树 的解法二 —— 先建字典树，再树上 DFS 统计
 *
 * 把单词列表逐个插进字典树：公共前缀只保留一份，走到头才开新结点，
 * 这样建出来的树正好满足「结点数最少」的条件。
 * 建完后从根出发 DFS 遍历整棵树，访问到的结点数（含根）就是答案。
 */

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

const int MAXN = 40005; // 结点总数不会超过文件总长度 32K，留出余量
const int SIGMA = 26;   // 只有大写英文字母

struct TrieNode {
    int next[SIGMA]; // next[c] = 沿字符 ('A' + c) 往下的儿子编号，0 表示没有
};
TrieNode node[MAXN]; // 动态化静态：静态大数组当结点池，按编号引用
int node_cnt;        // 已经开出的结点数，根结点固定编号 1

// 动态开一个新结点，返回它的编号
int new_node() {
    node_cnt++;
    memset(node[node_cnt].next, 0, sizeof(node[node_cnt].next));
    return node_cnt;
}

// 插入一个单词：已经存在的前缀直接复用，走到头才开新结点
void insert(const string &word) {
    int u = 1;
    for (size_t i = 0; i < word.size(); i++) {
        int c = word[i] - 'A';
        if (node[u].next[c] == 0) {
            node[u].next[c] = new_node();
        }
        u = node[u].next[c];
    }
}

// 以 u 为根的子树共有多少个结点（含 u 自己）——树上 DFS 遍历
int dfs(int u) {
    int cnt = 1; // 先把自己数上
    for (int c = 0; c < SIGMA; c++) {
        int v = node[u].next[c];
        if (v != 0) {
            cnt += dfs(v); // 有儿子就往下走，每条存在的边恰好走一次
        }
    }
    return cnt;
}

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

    node_cnt = 0;
    new_node(); // 结点 1 = 根，根不含字母

    string word;
    while (cin >> word) {
        insert(word);
    }

    // DFS 返回值就是整棵树的结点数
    cout << dfs(1) << '\n';
    return 0;
}

Python 版（同一算法，树用父亲-孩子表示法 fa / ch 存储）：

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90#!/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-12 00:00
# update_at: 2026-10-12 00:00

"""
trie_dfs.py：【例3-2】单词查找树 解法二的 Python 版 —— 先建字典树，再树上 DFS 统计

树用「父亲-孩子表示法」存：fa[u] 记父亲、ch[u] 记孩子列表，向上向下都 O(1)；
label[u] 记结点上的字母（根不含字母，记 -1），孩子按加入顺序排列。
单词逐个插入：公共前缀只复用已有结点，走到头才开新结点，所以结点数自动最少。
建完后 dfs(根) 返回整棵树的结点数（含根）。
"""

import sys

fa: list[int] = []          # fa[u]：u 的父亲；fa[1] = 0 正好表示"根没有父亲"
ch: list[list[int]] = []    # ch[u]：u 的孩子，按加入顺序
label: list[int] = []       # label[u]：u 上的字母（'A'=65 ... 'Z'=90），根记 -1
node_cnt: int               # 已经开出的结点数，根结点固定编号 1


def init(n: int) -> None:
    """把 1..n 清空，fa 全为 0（fa[root] = 0 正好表示"根没有父亲"）。"""
    global fa, ch, label, node_cnt
    fa = [0] * (n + 1)
    ch = [[] for _ in range(n + 1)]
    label = [-1] * (n + 1)
    node_cnt = 1            # 编号 1 = 根，根不含字母


def add_child(u: int, v: int) -> None:
    """u 是 v 的父亲：孩子挂到 ch[u]，父亲写进 fa[v]，加边 O(1)。"""
    ch[u].append(v)
    fa[v] = u


def find_child(u: int, b: int) -> int:
    """在 ch[u] 里找字母为 b 的孩子，没有返回 0（编号从 1 开始，0 表示不存在）。
    每个结点最多 26 个孩子，线性扫也是 O(1)。"""
    for v in ch[u]:
        if label[v] == b:
            return v
    return 0


def new_node(u: int, b: int) -> int:
    """动态开一个字母为 b 的结点，挂在 u 下面，返回它的编号。"""
    global node_cnt
    node_cnt += 1
    v = node_cnt
    label[v] = b
    add_child(u, v)
    return v


def insert(word: bytes) -> None:
    """插入一个单词：已有的前缀直接复用，走到头才开新结点。"""
    u = 1
    for b in word:
        v = find_child(u, b)
        if v == 0:
            v = new_node(u, b)
        u = v


def dfs(u: int) -> int:
    """以 u 为根的子树共有多少个结点（含 u）：dfs(u) = 1 + Σ dfs(孩子)。"""
    cnt = 1
    for v in ch[u]:
        cnt += dfs(v)
    return cnt


def solve() -> None:
    words = sys.stdin.buffer.read().split()   # 按空白切分，忽略空行

    # 结点数不超过 1 + 全部字符总数，先量好空间再一次 init
    init(1 + sum(len(w) for w in words))
    for w in words:
        insert(w)

    # DFS 返回值就是整棵树的结点数（含根）
    print(dfs(1))


if __name__ == "__main__":
    solve()

复杂度

时间：插入每个字符 $O(1)$ ，全部单词 $O(S)$ ；DFS 每个结点扫 26 个方向， $O(26 \times \text{结点数}) = O(S)$ 。合计 $O(S)$ 。
空间：结点池 $O(26 \times \text{结点数})$ ， $S \le 32\text{K}$ 时约 4 MB。

复杂度对比

	解法一：排序 + LCP	解法二：建树 + DFS
时间	$O(S \log n)$	$O(S)$
空间	$O(S)$ ，存全部单词	$O(26S)$ ，静态结点池
是否建树	否	是
附加产物	只有结点数	完整的字典树，可继续查找、遍历

两者的差别只在排序的 $\log n$ 和结点池的常数，本题 $S \le 32\text{K}$ ，两种写法都远远够用。只想拿答案选解法一；要接着在树上做别的事（单词查找、遍历序）选解法二。

总结

前缀即结点：最少结点数 = 去重后的非空前缀个数 + 1。这个观察让两种解法都能一次算清——要么排序后用相邻 LCP 累加，要么插入时让公共前缀只开一次点。
字典树的本质就是共享前缀：insert 里「有儿子就复用、没有才开点」这一句，正是题面「结点数最少」的实现。
树上 DFS 统计是通用套路：dfs(u) = 1 + Σ dfs(儿子)，每个结点访问一次，既能数结点，也能数叶子、求深度。