企业官网建设流程全解析

刷到一道蓝桥杯 2024 省 B 第二场的真题，题目叫“前缀总分”，题号 P12124，标签是“普及+”。看到“前缀”两个字，很多人的第一反应是暴力枚举每个字符串的所有前缀，然后去集合里数次数。这样做小规模数据没问题，数据稍微大一点就是稳稳的 TLE。这道题放在“普及+”档位，其实核心就一个：你有没有掌握字典树（前缀树）这个基础数据结构。今天我就借这道题，把前缀树的原理、实现和刷题里的实际坑一次讲透，顺便聊聊这类前缀问题在蓝桥杯里的常见变体。

1. 题目在问什么：从“前缀总分”四个字拆出算法方向

1.1 我理解的题意与样例推演

题面我印象里大概是这样的：给定 n 个由小写字母组成的字符串，定义一个前缀 p 的“得分”为 p 在全部 n 个字符串中作为前缀出现的次数。然后对每个字符串，它的“前缀总分”就是这个字符串所有前缀的得分之和。要求输出所有字符串的前缀总分之和。

请留意这个“所有字符串的前缀总分之和”不是把所有不同前缀的得分加起来，而是对每个字符串单独累加它的每个前缀的得分。举个例子，如果输入三个字符串：

3 a ab abc

手动算一遍：

• 前缀 “a” 在 3 个字符串中都出现，得分 3。
• 前缀 “ab” 在 “ab” 和 “abc” 中出现，得分 2。
• 前缀 “abc” 只在 “abc” 中出现，得分 1。

然后看每个字符串：

• “a”：只有一个前缀 “a”，总分 3。
• “ab”：前缀 “a” 得分 3，前缀 “ab” 得分 2，总分 5。
• “abc”：前缀 “a” 得分 3，前缀 “ab” 得分 2，前缀 “abc” 得分 1，总分 6。

最终答案是 3 + 5 + 6 = 14。

这个题目如果像我理解的这样，那它本质上就是在问：每个前缀在多少个字符串中出现过，然后把这些出现次数按字符串前缀路径累计一遍。你可以想象成有一棵“字典树”，每次插入字符串时，路径上每个节点都记录“有几个字符串以这个节点为结尾的前缀开头”，最后再拿着每个字符串往树上走一遍，边走过把节点计数累加。

当然，不同版本的题目可能求的东西略有区别，有些可能是只统计不同前缀出现次数之和，或者要求每个字符串单独输出自己的总分。但无论哪种，核心的数据结构都是字典树。如果你拿到的题面和我在文中描述的有细微出入，调整最后的累加规则就行，树的部分完全一样。

1.2 暴力做法的时间账：为什么非用 Trie 不可

先说暴力。最简单的思路是：枚举每个字符串 s 的所有前缀 substring(0, k)，再枚举所有字符串判断这个前缀出现了几次。假设 n 个字符串，总字符数加起来是 L，单个字符串平均长度是 len，那么光是枚举前缀就是 O(n * len)，每次判断出现次数还要 O(n * len)，总复杂度是 O(n² * len²)。当 n = 10^4，len = 10，这个量级就是 10^10 次起步，何况字符串比较还有常数，蓝桥杯的测试点根本跑不完。

再优化一点，用哈希表存所有前缀的出现次数：先把所有前缀截出来，加入哈希表计数，然后再次枚举每个字符串的每个前缀，去哈希表查次数。这样时间复杂度是 O(L)，看起来不错，但有两个隐患：一是枚举出来的前缀是独立字符串，生成子串本身要拷贝，内存开销不小；二是哈希表处理大量字符串键时，哈希碰撞和内存寻址的常数比较大，在极限数据下也不够稳。

字典树的做法则是把公共前缀共享起来，每个前缀在树上对应一个节点，出现次数直接存在节点里。插入一个字符串的时候，每走一步节点计数加一，就相当于把这条路径上所有前缀的出现次数都加了一。查询某个字符串的总分时，沿着这棵树走一遍，把每个节点的计数累加即可。总复杂度是 O(L)，而且完全不用生成子串，只消耗节点的索引和计数，常数极小。这就是这道题必须用 Trie 的根本原因。

2. 字典树原理：把“共同前缀”变成树上的共享路径

2.1 从查英文词典的比喻说起

你可以把字典树想象成一本特殊的英文词典。查单词 apple 的时候，你不会翻到 a 开头的每一个单词逐字比较，而是先找字母 a，再找 p，再找 p，一路往下走。这本词典的巧妙之处在于：所有以 a 开头的单词共享同一个 “a” 节点，所有以 ap 开头的单词共享 “a -> p” 节点，后面的分支再各自展开。

放到程序里就是一棵多叉树，根节点代表空串。从根节点出发，每条边对应一个字符。从根节点到某个节点的路径上的字符拼接起来，就是一个前缀。某个节点被经过的次数，就是该前缀在所有插入字符串中作为前缀出现的次数。

对比一下数组、哈希表和字典树处理前缀问题的区别，用一张表就能看得清楚：

2.2 节点结构、插入操作、查询操作的核心逻辑

字典树的每个节点只做两件事：记录通向子节点的指针，以及记录一些附加信息。对于这道题，附加信息就是“这个节点代表的前缀出现次数”。

一个常见的实现是每个节点开一个长度为 26 的数组，下标对应 26 个小写字母。为什么不是用哈希表存子节点？因为 26 个字母是确定且有限的，开数组访问是 O(1)，不需要算哈希，也不会有碰撞问题。如果你担心内存，后面我会示范两个优化写法：一个是静态数组版的“内存池”，另一个是链表式结构体数组。竞赛中我更推荐前者，因为 new 和 delete 在大数据量下既慢又容易出错。

插入过程很直观：从根节点开始，依次取出字符串的每个字符，如果当前节点没有这个字符对应的子节点，就新建一个；然后走到子节点，并把该节点的计数加一。这个计数表示“经过这里的字符串数量”，也就是此前缀的出现次数。

查询过程同样从根开始，沿着字符串的字符一路向下。如果是查询一个字符串是否出现过，就检查路径是否存在以及结尾节点的结束标记；如果是计算前缀总分，就在走的过程中把每个经过节点的计数累加起来。

这里有一个很容易犯迷糊的点：根节点的计数怎么处理？根节点代表空串，任何字符串都以空串为前缀。但在大多数题目里，空串不被算作有效前缀，所以插入时计数只从根节点的子节点开始加，根节点自身的计数保持 0，或者在统计答案时直接忽略根节点。后面我讲到代码实现时，你会看到这一点处理不好会导致答案多出 n。

3. 用字典树解决 P12124：完整推导与双语言实现

3.1 算法流程：一插一累，两次遍历

正式写代码之前，先把整体流程定下来。我们需要两轮遍历 Trie：

1. 插入阶段：读入每个字符串，从根出发，每经过一个节点就cnt[node]++。这一步完成后，cnt[node]就表示以该节点到根路径上的字符组成的前缀，在全部 n 个字符串中作为前缀出现的次数。

2. 统计阶段：再遍历每个字符串，从根出发，沿着字符走，每到一个节点就把cnt[node]累加到答案中。这里要注意，根节点不计入累加，因为空串不算前缀。

为什么能这么做？因为每个字符串的所有前缀，恰好对应它在 Trie 中从根到字符串末尾节点路径上的所有节点。第二遍遍历时，我们把每个前缀的出现次数累加进来，正好等价于题目要求的前缀总分。

如果想进一步压缩时间，可以在插入阶段就记录每个字符串的终止节点位置，统计阶段直接从根走到终止节点。但其实是同一件事，只是少走一遍字符判断。字符串总长度 L 一般也就几十万，两种写法差别不大。我下面给出更清晰的写法：插入时用nodeIndex记录每个字符串的末尾节点，统计时从根沿着 Trie 累加。

3.2 C++ 实现（静态数组版，不需要 new）

我平时刷题最常用的是静态数组写法。提前分配足够大的节点池，每个节点用next[26]存子节点下标，用cnt存前缀出现次数。新节点直接取tot++的下标，避免new带来的碎片化和性能损耗。

#include <bits/stdc++.h> using namespace std; const int MAXN = 1000005; int trie[MAXN][26]; // 子节点下标，0 表示不存在 int cnt[MAXN]; // 节点代表的前缀出现次数 int tot = 1; // 已使用的节点数，0 留给根节点 void insert(const string& s) { int u = 0; // 从根节点开始 for (char c : s) { int v = c - 'a'; if (!trie[u][v]) { trie[u][v] = tot++; // 新建节点 } u = trie[u][v]; cnt[u]++; // 每经过一次，该前缀出现次数加一 } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<string> words(n); for (int i = 0; i < n; ++i) { cin >> words[i]; insert(words[i]); } long long ans = 0; for (const string& s : words) { int u = 0; for (char c : s) { int v = c - 'a'; u = trie[u][v]; // 题目保证前缀一定存在，不会走到 0 ans += cnt[u]; // 累加此前缀的出现次数 } } cout << ans << '\n'; return 0; }

这段代码有几个细节值得强调：

• tot从 1 开始，根节点下标为 0，这样子节点下标如果是 0 就表示“不存在”，不需要额外初始化。统计阶段直接u = trie[u][v]，因为插入时该前缀肯定存在，不会访问到不存在的节点。
• ans必须用long long。如果 n 是 10^5，字符串平均长度 10，总前缀数量就是 10^6 级别，每个前缀出现次数最多 10^5，乘积是 10^11，int 根本装不下。这个坑我在限时训练里踩过，输出答案突然变成负数，排查半天才想起来是爆了 int。
• 数组开多大？一般用总字符数 + 10 就够了。比如总字符数 5*10^5，就开MAXN = 5e5 + 5。如果你不确定，就开大一点，蓝桥杯内存通常给 256MB，trie[ MAXN ][26]每个节点 104 字节，100 万节点大概是 104 MB，勉强可用。所以最好用动态写法或数组写法配合总字符数来定。

3.3 Python 实现（列表数组写法）

Python 刷蓝桥杯也很常见。用列表数组实现 Trie 是最平衡的方式。我提供两个版本：第一个是嵌套字典，写起来短，适合快速理解；第二个是列表数组，性能更好，推荐在正式比赛中使用。

先看嵌套字典版本，用dict存子节点，节点本身就是一个嵌套的字典结构：

class TrieNode: __slots__ = ('children', 'cnt') def __init__(self): self.children = {} self.cnt = 0 def solve(): n = int(input()) words = [input().strip() for _ in range(n)] root = TrieNode() for s in words: node = root for ch in s: if ch not in node.children: node.children[ch] = TrieNode() node = node.children[ch] node.cnt += 1 ans = 0 for s in words: node = root for ch in s: node = node.children[ch] ans += node.cnt print(ans) if __name__ == '__main__': solve()

嵌套字典代码很清晰，但每个节点都要维护一个字典对象，内存开销大，访问也有哈希开销。在数据量大的题目里，我更推荐用列表数组。用两个列表，trie存子节点下标，cnt存计数，跟 C++ 思路完全一样：

import sys def solve(): input = sys.stdin.readline n = int(input()) words = [input().strip() for _ in range(n)] trie = [[0] * 26] cnt = [0] tot = 1 def insert(s): nonlocal tot u = 0 for ch in s: v = ord(ch) - 97 if trie[u][v] == 0: trie[u][v] = tot trie.append([0] * 26) cnt.append(0) tot += 1 u = trie[u][v] cnt[u] += 1 for s in words: insert(s) ans = 0 for s in words: u = 0 for ch in s: v = ord(ch) - 97 u = trie[u][v] ans += cnt[u] print(ans) if __name__ == '__main__': solve()

这里nonlocal tot只适用于嵌套函数。如果你把insert提出来，可以用列表tot = [1]或者直接在主循环里展开，避免闭包变量作用域的问题。写 Python 时特别要注意sys.stdin.readline读取速度比input()快得多，蓝桥杯的 Python 组用input()遇到大数据时，读字符串本身就会浪费时间。

4. 复杂度、边界条件与实测中的坑

4.1 时空复杂度细算

插入阶段，每个字符串的每个字符都要走一遍，耗时 O(L)，其中 L 为所有字符串的长度总和。统计阶段又要走一遍所有字符串，同样是 O(L)。总时间复杂度 O(L)，常数很小，基本就是遍历两遍字符数组。

空间复杂度方面，节点数量最多是 L + 1（每个字符可能产生一个新节点），每个节点 26 个子节点指针外加一个计数。如果用静态数组，就是(L + 1) * (26 * 4 + 4)字节，L 为十万时约 10 MB，完全在可接受范围内。

这里的复杂度比普通哈希表方案的优势在于：不需要截取子串，不需要对每个前缀单独做哈希，全过程就是简单地数组下标跳转和整数累加。对极限数据，这两倍常数的差距可能决定了你是 AC 还是超时。

4.2 我踩过的几个坑

这个题看着简单，但实际提交时有不少细节会让你的代码挂掉。我把踩过的坑列出来，每条都是血泪经验。

long long 缺失。这是最隐蔽的。很多人在统计阶段用int ans，小样例跑得飞快，一提交全是 WA 或者奇怪的负数。我算过数据上限，n 取 10^5，总字符数 10^6，前缀总分最高能到 10^11 量级，必须用long long。

重复字符串。如果输入里有多个完全相同的字符串，比如三个"abc"，Trie 会在同一路径上走三遍，cnt累加三次。统计阶段每个字符串都独立累加，因此同一个前缀会被累计三次。这恰恰是题意要求的“作为前缀出现的次数”，不能去重。如果你用哈希表先对所有不同前缀计数，再去处理所有字符串，就会在重复字符串上出错。

空字符串。题目里的字符串都由小写字母组成，通常不会出现空串。但如果你测试自己的代码，不小心输了一个空串，插入函数会不执行循环，统计阶段也不累加，结果看似没问题，实际上如果你把根节点的 cnt 当成了前缀计数，答案就会多出 n 个空串贡献。好在这里根节点 cnt 没有被加过。

数组越界。C++ 静态数组如果开得太小，插入新节点时tot++会写越界。这往往不是立刻崩，而是在统计阶段读到错误数据。最稳的做法是先算总字符数，再开tot + 5的空间，或者直接开ALL_LENGTH + 10。我习惯提前读入全部字符串并计算总长度，再根据总长度初始化数组，一劳永逸。

4.3 用手动样例验证思路

用我前面给的样例3 / a / ab / abc，代码跑出来的结果和手算一样是 14。我再给你一个更容易暴露问题的小样例：

4 a a aa ab

手动计算一下，所有前缀出现次数：

• “a”：4 次（两个 “a”，一个 “aa” 和一个 “ab” 都以 a 开头）
• “aa”：1 次
• “ab”：1 次

四个字符串的分数分别是：

• “a”：4
• “a”：4
• “aa”：4 + 1 = 5
• “ab”：4 + 1 = 5

总和 18。你把这段输入喂给上述任何一段代码，如果答案不是 18，说明根节点计数或者重复统计逻辑出了问题。这种小样例最适合用来验证思维盲区。

5. 从“前缀总分”到一类题：字典树的高级玩法和变种

5.1 变种一：求两两字符串之间最长公共前缀长度总和

前缀总分只是 Trie 的一种简单应用。每年蓝桥杯和 ICPC 都爱考另一种变体：给定 n 个字符串，求所有无序对(i, j)的最长公共前缀（LCP）长度之和。

这种题也是用 Trie，但统计方式完全不同。在 Trie 上，每个节点代表一个公共前缀。两个字符串的 LCP 长度，就是它们在 Trie 上从根开始能共同走过的深度。对于节点 u，假设size[u]是以 u 为根的子树中包含的字符串数量，那么经过节点 u 的字符串对就是C(size[u], 2)，这些字符串对的 LCP 至少为depth[u]。用差分思想，每个节点贡献C(size[u], 2)给答案，节点深度不需要额外考虑，因为一条路径上所有节点的贡献会自动累加成长度。

具体做法：插入时在终止节点打标记，表示子树里包含这个字符串。然后用 dfs 自底向上合并size，同时累加C(size, 2)。这个复杂度同样是 O(L)，但思维难度比前缀总分高了一截。如果你能把这道题做明白，前缀树的大部分基础套路就算掌握扎实了。

5.2 变种二：用 0/1 字典树解决异或最大值

Trie 还能存二进制位，这就是大名鼎鼎的 0/1 Trie。给定一个数组，求两个数的最大异或值，经典解法是把每个数的二进制从高位到低位插入 Trie，然后依次查询每一位，尽量走向与当前位相反的节点，这样能让异或结果在高位尽量为 1。贪心的正确性在于二进制高位权重更大。

蓝桥杯前几年出过不少这类题，比如“最大异或对”以及一些新定义运算的模拟题。如果你已经掌握了字符串 Trie，转换到 0/1 Trie 只需要把“字符集”从 26 个字母改成 0 和 1，其余结构完全一致。这种举一反三的能力，在省赛和国赛里非常重要。

5.3 工程场景中的实际应用

别以为 Trie 只在竞赛里出现。它在真实工程里的身影也很常见：

• 输入法的前缀联想：你敲一个拼音，后面的候选词就是所有以该拼音为前缀的短语，本质是 Trie 前缀查询。
• 搜索引擎的关键词补全（autocomplete）：搜索框里每输入一个字符，后台就会返回一堆以当前输入为前缀的热搜词，很多实现里都有 Trie 参与。
• IP 路由表最长前缀匹配：路由器匹配 IPv4 地址时，要在一个庞大的前缀表里找最长匹配项，这就是二进制 Trie 的典型应用。
• 敏感词过滤系统：把敏感词建一个 Trie，然后对文本进行扫描，命中一个节点就标记一次，可以高效地把所有敏感词替换成星号。

所以，哪怕你不打算在竞赛路线上走太远，把 Trie 吃透对后续学习数据结构、算法设计和理解现代网络系统也有直接的帮助。

6. 最后分享一点实际训练中的体会

我最早刷 P12124 时，其实没有直接想到 Trie，而是先写了一个map<string, int>版。本地跑过简单的样例，感觉挺顺的，结果提交后第三个测试点就超时。后来换成 Trie，同样的数据量从 2 秒多降到了 0.1 秒。这个对比让我印象很深：处理前缀类问题时，Trie 的价值不在于“奇技淫巧”，而在于它把“字符串的公共部分”变成了一次遍历里的共享路径，省掉的是大量重复比较。

如果你打算准备蓝桥杯或类似比赛，建议把这题亲手实现三遍：第一遍用嵌套字典写，理解结构；第二遍用静态数组写，体会性能；第三遍尝试改成求 LCP 总和那道变体，巩固迁移能力。等你遇到“字符串前缀”相关题目，脑子里的第一反应就是“这题能不能用 Trie”的时候，这个知识点就算真正过关了。