魔族密码

题意

从单词表中选出尽量多的词，使前一个词始终是后一个词的前缀。

思路

固定链的最后一个单词 word。所有出现在词表中的 word 前缀天然按长度互相包含，所以把它们全部选上就是最优链。

因此只需把单词放入集合，对每个 word 枚举所有非空前缀并统计有多少个也在集合中，取最大值。

单词长度最多 75，切片产生的额外常数很小；相比手写 Trie，这种写法更能体现 Python 的字符串和哈希集合优势。

字典树（Trie）视角

枚举前缀在集合中查找已经够用，但 Trie 能更直观地展现前缀嵌套的关系。以样例 i → int → integer → intern → internet 走一遍。

初始：trie = {}，根节点是空字典。每个节点存子节点和可能的 # 标记（单词结尾）。

插入 "i"：创建 trie['i'] = {}，标记 #。

python

1trie = { 'i': { '#': True } }

走到 # 的路上看到了 0 个已结束的单词，加上自己 → 链长 1。

插入 "int"：沿已有节点 i 往下，读到 n、t 时依次创建。

python

1
2
3
4trie = { 'i': {
    '#': True,          ← 路上看到 1 个
    'n': { 't': { '#': True } }
} }

路上看到 i 的 #（1 个），加上自己 → 链长 2。

插入 "integer"：走到 int 节点的 # 时又累加一次。

python

1
2
3
4
5
6
7trie = { 'i': {
    '#': True,
    'n': { 't': {
        '#': True,      ← 路上又看到 1 个
        'e': { 'g': { 'e': { 'r': { '#': True } } } }
    } }
} }

路上看到 i 和 int 两个 #，加上自己 → 链长 3。

插入 "intern"：在 e 处分叉，与 integer 走不同分支。

python

1
2
3
4
5
6
7
8
9
10trie = { 'i': {
    '#': True,
    'n': { 't': {
        '#': True,
        'e': {                     ← 分叉点
            'g': { 'e': { 'r': { '#': True } } },   ← "integer"
            'r': { 'n': { '#': True } }              ← "intern"
        }
    } }
} }

路上看到 i 和 int 两个 #，加上自己 → 链长 3。

插入 "internet"：沿 intern 路径继续往下。

python

1
2
3
4
5
6
7
8
9
10
11
12
13trie = { 'i': {
    '#': True,
    'n': { 't': {
        '#': True,
        'e': {
            'g': { 'e': { 'r': { '#': True } } },
            'r': { 'n': {
                '#': True,          ← 路上看到第 3 个
                'e': { 't': { '#': True } }
            } }
        }
    } }
} }

路上看到 i、int、intern 三个 #，加上自己 → 链长 4。ans = 4。

本质：每个单词沿着 Trie 往下走时经过的 # 数，就是它有多少个前缀已在词表中。加上自己，就是以它结尾的最长词链长度。

Python 知识

set(data[1:]) 建立平均 $O(1)$ 查询的单词集合。
word[:length] in words 同时使用字节串切片与集合成员测试。
内层 sum(...) 统计布尔值，外层 max(...) 取所有链的最大长度。
生成器表达式不保存所有中间计数。
字典树可借助嵌套 dict 实现，用特殊键 '#' 标记单词结尾，省去手写节点类。
DP 的 str.startswith 直接判断前缀关系，配合字典序保证的先后顺序。

代码

四种做法：

集合 + 前缀枚举（main.py）：最短，Python 风格， $O(nL^2)$
字典树（main-trie.py / main.cpp）：路径上数 #， $O(nL)$ ，适合理解前缀嵌套
DP（main-dp.py）：startswith 向前查找， $O(n^2L)$ ，N=2000 可过
DP（main-short.py）：用 dict 代替 dp 数组，利用前缀查哈希表，极致简洁

python

1
2
3
4
5
6
7import sys


data = sys.stdin.buffer.read().split()
words = set(data[1:])
print(max(sum(word[:length] in words for length in range(1, len(word) + 1))
          for word in words))

python

1
2
3
4
5
6
7
8
9
10
11
12import sys

# 1. 一次性读取所有输入，split() 自动处理换行，[1:] 直接过滤掉第一行的数字 N
words = sys.stdin.read().split()[1:]

dp = {}
for w in words:
    # 2. 生成当前单词的所有前缀 w[:i]，去哈希表查表，取最大值 + 1
    dp[w] = max([dp.get(w[:i], 0) for i in range(1, len(w))], default=0) + 1

# 3. 输出最长词链长度
print(max(dp.values()) if dp else 0)

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# 前置知识：每个单词按字典序输入，保证前缀一定在前面出现
# 用字典树，插入时统计路径上遇到几个已结束的单词（即前缀）
import sys

data = sys.stdin.buffer.read().split()
n = int(data[0])
words = [w.decode() for w in data[1:]]

trie = {}  # 根节点
ans = 1

for w in words:
    node = trie
    chain = 0

    # 沿着 w 的每个字符在字典树中往下走
    for ch in w:
        if ch not in node:
            node[ch] = {}  # 新建子节点
        node = node[ch]

        # 路过的节点如果是某个已插入单词的结尾，说明这个单词是 w 的前缀
        if '#' in node:
            chain += 1

    # 当前单词自己也算进去
    chain += 1

    # 标记当前单词的结尾
    node['#'] = True

    ans = max(ans, chain)

print(ans)

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
25from functools import partial
import sys

def flow(value, *steps):
    for step in steps:
        value = step(value)
    return value

data = sys.stdin.buffer.read().split()
words = [w.decode() for w in data[1:]]

# print(words)
dp = [1] * (len(words) + 5) 
ans = 1
for i,w in enumerate(words):
    # print(i,w)
    for j in range(i):
        pre_w = words[j]
        if w.startswith(pre_w):
            dp[i] = max(dp[j]+1, dp[i])
            ans = max(ans, dp[i]) 
print(ans)

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/**
 * 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-07-23 17:48
 *
 * 魔族密码 - Trie 解法
 *
 * 每插入一个单词，沿 Trie 往下走时统计路径上遇到了几个
 * 已标记为单词结尾的节点（即当前单词的前缀）。
 * 链长 = 路径上遇到的前缀数 + 1（自己）。
 * 在所有链长中取最大值。
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 150000 + 5;
int trie[MAXN][26];
bool is_end[MAXN]; // 标记节点是否为某个单词的结尾
int node_cnt = 1;  // 根节点编号为 1

int get_new_node() {
    ++node_cnt;
    return node_cnt;
}

// 插入单词 s，返回以 s 结尾的最长词链长度
int insert_word(const string &s) {
    int u = 1;
    int chain = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (trie[u][c] == 0) {
            trie[u][c] = get_new_node();
        }
        u = trie[u][c];
        // 沿途遇到的 is_end 标记都是 s 的前缀
        if (is_end[u]) {
            ++chain;
        }
    }
    // 标记 s 自己为单词结尾
    is_end[u] = true;
    ++chain; // 加上自己
    return chain;
}

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

    int n;
    cin >> n;
    int ans = 0;

    for (int i = 1; i <= n; ++i) {
        string s;
        cin >> s;
        ans = max(ans, insert_word(s));
    }

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

复杂度

做法	时间	空间
集合 + 前缀枚举	$O(nL^2)$	$O(nL)$
字典树（Python / C++）	$O(nL)$	$O(\sum L \times 26)$
DP（main-dp.py）	$O(n^2L)$	$O(n)$
DP（main-short.py）	$O(nL^2)$	$O(nL)$

最大单词长度 $L\le75$ ，四种均能通过。

总结

当键本身就是完整短字符串时，Python 集合往往比节点级 Trie 更短、更清楚；Trie 的优势在于理解前缀嵌套结构和稳定的时间表现；DP 在 N 足够小（2000）时也是可选项。

目录

题意

思路

字典树（Trie）视角

Python 知识

代码

复杂度

总结