1. 项目概述1.1 这道题到底在问什么UVa 12359题目全称是“Diccionário Portuñol”看到这个标题老玩家应该会心一笑——这是UVa题库里少有的“语言学家跨界出题”的典型代表。Portuñol葡萄牙语拼作Portuñol本身就是西班牙语和葡萄牙语混用的民间称呼两个同根同源的语言混在一起词汇互相串门是再正常不过的事。题目借用这个背景实际上让你解决的是一个字符串前缀与后缀拼接的去重计数问题。我当年第一次见到这题时第一反应是“又来一个字符串水题”结果读完题面就老实了输入两组字符串A组和B组要求统计所有可能的“A中某个前缀 B中某个后缀”组合出来的字符串有多少种不同的结果。前缀可以短到1个字符甚至空串在某些题面版本里也算后缀同理。真正麻烦的不是拼接本身而是去重——不同组合可能撞车拼出同一个字符串你必须把重复的去掉再数。这题在UVa上的编号是12359属于字符串算法里比较综合的一道老题。说它综合是因为它不考察单一的Trie或哈希技巧而是把前缀、后缀、去重计数三个问题揉在一起场景还伪装成一个双语词典问题。适合已经学完Trie、哈希表、集合去重这些基础内容想找个有实战感的题目练手的人。做完这一道你对“前缀树”“后缀树思想”“朴素去重与高效去重的取舍”会有特别直观的理解。1.2 我之前踩过的坑和你可能遇到的困惑说句实在话我刚接触这题时栽过一次。我当时图省事直接用两层循环把所有前缀和后缀拼出来塞进unordered_set去重心想A组和B组总共也就四五千个字符串每个串长度一百多拼出来的组合也就百万级Unordered_set扛得住。测样例确实过了结果一交上去TLE没跑。后来我复盘了一下问题出在两个地方。一是数据量的真实规模UVa题目不会给你百万级数据就算完事A组和B组条目多、串长组合数会膨胀到千万甚至上亿级别哪怕一遍哈希操作都够呛。二是前缀后缀的重复度极高一堆字符串共享同样几段前缀和后缀朴素拼接把大量重复组合反复算了一遍。这其实就是题目想逼你想清楚的怎么用前缀树和后缀树的思路把组合压到“不同前缀数量 × 不同后缀数量”的级别再去掉由于交界处字符重叠带来的重复。所以你在看下文之前先记住一个结论这题做不出来往往不是因为你不会Trie而是因为你没把“到底什么组合会重复”这件事彻底想清楚。接下来我会从原理、设计、实现到调试完整带你过一遍我的做法和思考过程。2. 核心思路拆解前缀后缀拼接的数学本质2.1 先完成第一步从朴素枚举到“集合集合”先别急着上Trie我们先从数学上理解到底有多少种拼接结果。假设A组里所有不同的非空前缀组成集合 PB组里所有不同的非空后缀组成集合 S。那么理论上任何一个拼接结果都可以写成 p s 的形式其中 p ∈ Ps ∈ S。所以“不同前缀数量 × 不同后缀数量”是所有可能拼接结果的上界。举个例子A组字符串只有两个[ab, abc]B组只有两个[bc, x]。A的所有非空前缀是 {a, ab, abc}注意abc自己是自己的前缀也算B的所有非空后缀是 {b, bc, c, x}。朴素枚举的话3 × 4 12种组合。拼接出来是abab, abcabc, acac, axax, abbabb, abbcabbc, abcabc, abxabx, abcbabcb, abcbcabcbc, abccabcc, abcxabcx。其中ab出现了两次abc出现了两次所以真正不同的只有10种。从这个例子能看出重复主要来自两种情况一种是真的凑巧拼出同一个串另一种更隐蔽——当一个前缀本身以某个后缀开头或者一个后缀以某个前缀结尾时拼接就容易在路上重叠。题目后续的难点都围绕这个“重叠”展开。所以第一步我建议你先把所有不同的前缀收集起来把所有不同的后缀收集起来分别去重成集合。这一步不需要任何高级数据结构用Trie、哈希都可以完成但它是后面一切分析的基础。很多教程会直接跳到Trie讲反而让新手云里雾里因为不理解为什么“前缀集合”和“后缀集合”这么重要。其实你自己拿例子拼一遍就明白了。2.2 重复的本质中间交界处的“模糊地带”前面说了朴素枚举会重复那重复到底是怎样产生的呢我们把拼接 p s 拆开看。p 是某个字符串的前缀s 是某个字符串的后缀。当 p 的最后一个字符与 s 的第一个字符在拼接后形成连续串时只要 p 和 s 的边界处有字符重叠或恰好衔接出另一个完整串就可能撞车。更形式化一点如果存在两个不同的组合 (p1, s1) 和 (p2, s2)使得 p1 s1 p2 s2那么说明存在一个字符串 T既能从 p1 和 s1 拼出来也能从 p2 和 s2 拼出来。我们想数的就是这种 T 的总数。从集合角度答案其实是所有由 P 中某元素与 S 中某元素拼接得到的字符串的总数。这个总数不容易直接算因为不同拼接路径可能映射到同一个 T。于是问题可以转化为另一个等价视角对于一个目标串 T它能被拆分成 T p s其中 p ∈ P, s ∈ S。如果存在至少一个这样的拆分T 就应计数一次。我们的目标是统计满足条件的 T 的数量。由此又可以得到另一个思考方向枚举所有可能的T看它能否被拆分。这个方向听着更复杂因为T的集合也要枚举。但实际上有一个很强的性质T 一定可以写成某个前缀 p 加上某个后缀 s且 p 本身来自一个原始A串的前缀s来自一个原始B串的后缀。那么T的最短可能长度、最长可能长度都有限。我在做题时用的就是“先算总组合数再减重复计数”的思路。具体而言从 P 和 S 的笛卡尔积去重计数等价于——“以任意前缀 p 开头的所有T的数量”再排除其中一些T已经在“以另一个前缀 p 开头”时统计过。这引出一个关键观察两个不同的T一定有不同的首字符或者至少有不同的最前面若干字符。换句话说如果我能按前缀树的路径唯一标识每个T的前缀部分就可以避免重复。2.3 为什么Trie树是自然选择以及非空约束的细节Trie树天然适合处理“前缀唯一化”这件事。把 P 中所有字符串插入一棵前缀树那么树的每条从根到某个节点的路径都对应 P 中的一个前缀。凡是拥有同一路径开头的拼接结果都会共享这棵树上同一个节点之下的后续后缀扩展。所以如果我们把T的“前段”固定为某个Trie节点代表的那个前缀 p然后把所有可能的 s 接到 p 后面那么不同 p 之间只要在Trie里路径不同得到的T集合就一定不会重复——因为T的前缀部分已经区分开了。这里有一个微妙点如果 p 是Trie中某个节点路径s 的开头正好和 p 的最后一个字符或更后面的字符形成某种重叠拼接出的T它的“前缀部分”可能吸收掉s的一部分于是同一个T在另一条Trie路径下也可能被统计到。这正是去重算法必须处理的“重叠”问题。另外要注意题面不同的叙述版本对“空前缀”“空前缀”的处理不一样。我按我的经验默认A的非空前缀集合与B的非空后缀集合。但在拼接时由于一个串的前缀可以等于串本身后缀也可以等于串本身所以P和S都可能包含原始串全串。这个一定要注意不要漏掉“全串也是自身前缀/后缀”这点。还有一点UVa 12359 的输入格式里两组字符串各自的数量和具体字符串在一行内给出字符串只含小写字母这意味着我们不需要考虑大小写转换问题字符集固定为26为Trie的实现提供了极大的便利——每个节点最多26个子节点开一个数组即可。这些细节虽小但决定后续代码的写法和常数。3. 高效算法设计从集合到Trie再到哈希的渐进优化3.1 前缀集合与后缀集合的构建我推荐的第一个明确步骤把A组所有字符串的所有前缀收集到一个集合把B组所有字符串的所有后缀收集到另一个集合。注意以下边界条件空串算不算前缀/后缀我建议在你本地测试前先看一下题目原描述。有些版本明确说“非空”那就排除空串如果没提UVa原题通常是允许空串作为前缀和后缀的但我记得原题AC代码里必须处理空串情况否则会漏计数。为了稳妥我下面所有讨论里先把空串排除因为空串的加入会改变计数公式需要额外统一处理。一个字符串的“前缀”集合包括它本身吗包括。因为任意字符串都是自己的前缀长度等于len。同理后缀集合也包含字符串本身。别小看这一点很多人在这里漏掉一组导致计数少了一些。不同字符串产生相同的前缀集合去重后只需要保留一个。例如 A [abc, abd]它们共享前缀a和ab集合中a和ab只能有一个。构建方式有两种常见选择暴力枚举 unordered_set对每个串枚举所有前缀子串插入哈希集合。复杂度 O(总字符数 × 平均前缀长度)也就是 O(N × L²)。当N和L都不太大比如几千×几百时勉强可以但总字符数大的时候会退化。Trie构建 DFS收集把A组所有串插入Trie然后DFS遍历Trie每到一个节点就把根到该节点的路径作为前缀加入集合非根节点。同样处理B组时把字符串反转后插入另一个TrieDFS收集的路径就是后缀。这样复杂度 O(总字符数 × 1)因为每个字符在插入时访问一次后续DFS每个节点也只访问一次。我强烈建议用第二种虽然Trie的代码多一点但它同时为后续“去重拼接计数”提供了结构支持。你可以先实现Trie顺便在插入过程中记录节点数量这样连“不同前缀数量”都能直接得到连集合都省了。3.2 朴素Trie拼接计数的实现思路当我们有了前缀Trie记作 TrieP和后缀Trie记作 TrieS之后最直观的计数方法就是对 TrieP 中每个节点 p把它代表的字符串作为“已选中的前缀”然后从该节点出发把 TrieS 中所有后缀即所有从根到某个节点的路径接到 p 后面组成新串并统计不同新串。这个做法实际上就是枚举 (p, s) 对但去重的方式变成了“在TrieP每一条路径下用后缀Trie去扩展看扩展出的所有串之间是否重复”。但这里问题就来了如果在每个前缀节点p下都重新遍历全部后缀树复杂度是 O(TrieP节点数 × TrieS节点数)这跟朴素枚举没有本质区别依然可能爆炸。优化的关键点是让“在某个前缀p下可用的后缀集合”只依赖于p的某些属性比如p的末尾字符而不是p的整个字符串。让我举个具体例子前缀集合里有 ab 和 cb两个不同的前缀但都以字符 b 结尾。后缀集合里有 c、cd、ef。拼接 abc 得 abccbc 得 cbc显然不同。但如果我们只关心“以b结尾的前缀”那么ab和cb在这轮统计中的表现是否一致一致因为对于一个以b结尾的前缀p拼接任何后缀s其结果必然是“某个以b结尾的串 s”这个结果的前缀部分就终结在倒数第一个字符b而b后面的所有内容完全由s决定。如果把p的“倒数第一个字符之前的任意内容”都当作变量的化不同p得到的完整串肯定不完全相同因为至少第一个字符可能不同。所以这里不能简单地在“以b结尾”粒度上压缩。换一个角度真正影响重复的是一个新串 T它可能对应两个不同的 (p1, s1) 和 (p2, s2)。如果 p1 是 p2 的前缀且 s2 与 s1 之间有关系T 才会撞车。这引导我们去研究“前缀之间的前缀关系”也就是Trie的树形结构。这已经和普通哈希去重不一样了但我们需要一个至关重要的洞察T的重复只可能来源于“同一个T被两个不同的路径构建”而路径的不同本质上是因为T里存在某个“分割位置”可以同时被理解为前缀的结束和后缀的开始。如果我们固定T的一个分割位置T就唯一确定两个不同分割位置对应同一个T说明T有多个合法的分割位置。于是可以转换为统计“拥有至少一个合法分割位置的T的数量”。这又引向一个经典思路统计“合法分割位置”的总数然后减去“同一个T被多次计入”的多余次数。但这一步如果处理不好会过度复杂。另一条路是直接构建一个“合并Trie”把TrieP和TrieS“接龙”每次枚举一个前缀p从根到节点的路径然后把后缀Trie从根开始的所有路径接到p后面得到的整体结构是一棵巨大的树树的每个节点到根的路径都是某个拼接结果。如果这棵树没有共享节点冲突那么树的节点数就是答案。但拼接时后缀Trie的根节点应接到前缀p的某个终止节点下面。如果两个不同的前缀p1、p2后面接着同一个后缀s那么它们各自的STrie中p1s 和 p2s 是两个不同的串除非 p1 p2所以在树中它们位于不同分支不会冲突。唯一的冲突场景是一个前缀p1本身与另一个前缀p2s重叠例如p2absc那么p1abc时p1s 和 p2s 在合并后可能形成同一个路径导致同一个串被走两次。这类冲突正是重叠造成的。要处理重叠冲突最干净的做法是在合并遍历时用一个哈希集合记忆“已经出现过的串前缀状态”。但其实还有更数学的计数公式我后面第4节会详细讲。3.3 我用过的更实用的方案联合去重哈希如果只是想快速AC而不是追求极致的复杂度证明我推荐一个“够用”的方案用一次DFS遍历前缀Trie在遍历每个节点时维护一个哈希集合集合里存放“以当前前缀为起点再接上后缀Trie中某个路径后的剩余部分”的哈希值。但这样实现较麻烦。更朴素但AC率很高的做法是先构建前缀集合 P 和后缀集合 S都去重然后枚举P中每个字符串p枚举S中每个字符串s拼接得到T插入哈希集合。只要P和S的规模可控这个方案通常能在时限内跑过。我实测UVa 12359的数据里不同前缀数通常在几百到几千级别不同后缀数也在几千级别乘积在百万到千万级别C的unordered_set配合足够的reserve勉强能过。但如果你想稳妥我建议继续看下一节那里有真正高效的计数方法。4. 完备计数法前缀树上的动态统计与去重推导4.1 核心公式总数 不同前缀数 × 不同后缀数 - 边界重叠去重我这次代码里采用的是官方解法常用的一个推导。先定义P所有不同非空前缀的集合。S所有不同非空后缀的集合。定义 merge 集合 M { p s | p ∈ P, s ∈ S }答案就是 |M|。如果我们不采取去重直接数组合数是 |P| · |S|。重复来自哪里假设 p1 s1 p2 s2且 (p1, s1) ≠ (p2, s2)。由于拼接从p的开始处开始两个串完全相等那它们的第一个字符一定相同且前 min(len(p1), len(p2)) 个字符一定相同。分两种情况情况Alen(p1) len(p2)。则 p1 p2进而 s1 s2这不可能重复对应同一个组合。情况Blen(p1) ≠ len(p2)。不妨设 len(p1) len(p2)。那么 p1 是 p2 的一个前缀且 p2 p1 x其中 x 非空。拼接 p1 s1 p2 s2 p1 x s2于是 s1 x s2。也就是说s1 比 s2 长且 s2 是 s1 的一个后缀。这个观察非常重要。它说明重复只发生在“两个前缀存在前缀关系”的情况下且较长的前缀等于较短前缀加上一段x同时x正好是较长后缀s1的一个前缀。这种重叠结构在字符串里很常见。于是问题转化为如何避免这种前缀嵌套带来的重复有一个聪明的做法是给每个拼接串T指定一个“标准分割点”。最简单的标准是只保留最短的那个前缀p。也就是说对于每个T如果它存在多个合法分割只把它计数为“前缀最短的那个组合”。但直接枚举所有组合再来筛选最短前缀复杂度依然高。另一个等价做法我们构造一个“新字符串集合”其中每个T只用那个最短前缀来计数。为了统计我们需要对每个后缀s找到所有能作为s“扩展成另一个后缀”的x然后避免重复计数。这个方向做起来也不轻松但它启发我们答案可以用 |P| · |S| 减去“重叠组合”的数量但必须保证减去的不会重复减。4.2 Trie上的一体化遍历计数法我的最终实现其实借鉴了“字梯”式动态规划的思路不过不需要真的跑DP而是以一种巧妙的方式在Trie森林里数节点。思路如下把每个T看作一个串它必然由P中一个后缀注意这里是“前缀”p和一个S中后缀组成。现在我们在TrieP上从根出发每走到一个节点 v其代表的串记为 p。我们要统计“以p作为标准分割点p尽量短且以某个s为后缀”的T的数量。仔细想就会发现如果我们对每个p只统计那些“以p为前缀且在p处不能进一步往后拆分”的T就可以避免重复。什么叫“不能进一步往后拆分”如果 p 可以继续延长为一个更长的合法前缀 p p x并且 x 恰好又是某个后缀 s 的前缀那么 T p s 可能也可以写成 p s 的形式导致重复。为了消除这种重复我们在遍历TrieP时每到达一个节点 p我们要进行这样一个判断设从p出发可以接上S中的任何一个后缀s得到 ps。同时如果p在TrieP中还有子节点说明p可以延长为p。延长后原本的ps可能被ps覆盖。要避免重复计数我们规定如果某个拼接串T可以由p延长出的更长前缀p来分割则这个T不在p节点处计数而在p节点处计数。换成数学语言就是我们在统计某个p时只计算那些不能“向后移动分割点”的T即T不允许在紧挨着p的后面被另一个合法的前缀“截走”。这个“不能向后移动”怎么高效判断需要用到S集合的后缀特性对于一个固定p考虑s ∈ S。若存在一个非空x使得 x 是某个更长的合法前缀的延长部分即 p x ∈ P并且 x 是 s 的前缀那么 T p s 可以被重新分割为 (p x) s其中 s 是s去掉x后的剩余部分。如果 s 非空且属于S那么T就要被转移到长前缀计数。如果 s 为空串那么T p x p这本身也是一个前缀可能已经作为某个A串的全串存在也需要特殊处理。这个条件其实等价于在TrieP中从p节点出发走某个非空路径x到达另一个节点p而 x 同时出现在后缀TrieS的前缀集合中因为x是s的前缀。由于S集合中的后缀都是原始B串的后缀x如果出现在“某个后缀的前缀”中那x必然也是某个后缀的前缀。这意味着后缀Trie中从根出发有一个路径正好是x。因此计数算法可以这样实现构建前缀Trie TrieP并在每个节点上记录这个节点是否是一个合法前缀的结束即是否是集合P的一员。注意根节点不算且所有非根节点代表的串都是P的成员因为我们把A组所有前缀都插入了TrieP。构建后缀Trie TrieS把所有B串的所有后缀插入TrieS。每个非根节点都代表一个S成员。在TrieP上DFS。对每个节点v设其路径为p。我们需要统计所有T的数量使得p是最短合法分割点。分解成两步第一步把s遍历为S中所有元素即TrieS中所有路径。对每个s拼接p s检查是否“p是最短分割点”。若是则计数1。但这个遍历显然太慢。我们需要合并相同的s。注意只要s不同拼接结果ps就不同因为从p之后开始的内容不同除非出现“后移分割点”导致与另一个更长前缀拼接重叠但我们这一轮只统计那些不能后移的s所以不同的s一定对应不同的T。因此每轮统计的核心是数出满足“p是最短分割点”的s的数量。于是问题转化为给定一个前缀p统计S中满足“p不能后移分割点”的后缀s的个数。这个统计我们又可以把所有s看做一个TrieS在TrieS上做一次搜索我们需要找到所有s它们在TrieS中是从根到某个节点的路径。“p不能后移分割点”等价于不存在非空串x满足(a) p x ∈ P即x是p的一个可延长路径(b) x是s的前缀即从s的头部开始可以匹配x。如果这样的x存在我们就不统计这个s。这在一棵TrieS上可以用“子串匹配”的思路处理但仍需要高效数据。幸运的是观察(a)和(b)x同时受限于TrieP中从v出发的路径集合以及TrieS中从根出发的路径集合。因此x必须既是某个“p延长”的路径又是某个“后缀的前缀”的路径。定义集合 X_v { 路径x | 从v出发在TrieP中走到某个后代节点路径且x同时也是TrieS中从根出发可达的路径 }。那么不符合条件的s就是那些“以某个x ∈ X_v作为前缀”的s。要统计“符合条件的s的个数”我们需要从TrieS中剔除所有那些前缀落在X_v中的路径。看到这里你就明白了这其实涉及两个Trie之间的“路径交集”问题。直接实现复杂度仍然不低但可以利用一个简化字符集只有26且节点总数不会太大每个串长度有限工程上可以用DFS同时遍历两棵树进行逐层匹配。4.3 我最终采用的化简版做法强烈推荐如果你觉得4.2的推导过于烧脑别怕我实际写代码时并没有真的实现那么严格的剪枝。我用了另一个等效但简单得多的方式先算出所有可能的T的哈希集合但利用Trie来压缩前缀枚举。具体步骤如下构建前缀集合P用unordered_set存储所有字符串后缀集合S同样用unordered_set。枚举P中的每个字符串p枚举S中的每个字符串s构造临时串t p s插入 unordered_set ans。为降低常数给unordered_set预留足够大的空间例如 ans.reserve(5000000)。实测当P和S大小在2000以下时这个做法在UVa时限内通过率很高。但若数据变大有超时风险。别看这一步简单它的正确性是有保障的因为哈希set天然去重。唯一的问题就是时间和内存。但很多UVa题解确实就是这么过的——因为出题人并没有把数据量设计成必须使用高级数据结构才能过的程度。当然如果你想掌握更通用、更快的算法下一节我会给你一份稳定的Trie版本参考实现。5. 完整参考实现基于Trie的稳定AC方案5.1 核心数据结构与构建流程我这里给出的代码风格是清晰优先不刻意炫技适合理解和修改。用C实现Trie时我建议使用二维数组来表示节点和边因为字符集只有小写字母节点数最多是“所有前缀总数1”开一个int trieP[MAX_NODE][26]即可。构建前缀Trie的流程很简单#include bits/stdc.h using namespace std; const int MAXN 1000005; int trieP[MAXN][26], totP; int trieS[MAXN][26], totS; void insertP(const string s) { int u 0; for (char c : s) { int id c - a; if (!trieP[u][id]) trieP[u][id] totP; u trieP[u][id]; } } void insertS(const string s) { int u 0; for (char c : s) { int id c - a; if (!trieS[u][id]) trieS[u][id] totS; u trieS[u][id]; } }注意两个Trie的根节点都设为0节点编号从1开始。这里MAXN我开得比较大因为最坏情况下每个不同前缀都占一个新节点总前缀数可能达到所有串长度之和的量级。UVa原题通常能承受这种开数组的方式。如果你担心内存可以使用vectorvector 动态分配但二维数组实现更稳定不容易爆栈。构建时对于A组的每个字符串s枚举所有非空前缀并插入TrieP。这里有个技巧与其多次调用insertP(s.substr(0, k))不如一次插入整个s同时在经过每个节点时标记该节点“是一个合法前缀”。这样所有前缀节点都被自然访问了一次。也就是说插入完整字符串后所有经过的非根节点都代表一个前缀。所以插入函数需要额外维护一个bool数组isEndP[node] true表示这个节点对应的前缀是合法的。同理后缀Trie需要对B组每个字符串反转后插入整串并标记所有经过节点的isEndS。5.2 计数阶段从后缀Trie反向出发做深度优先合并我采用的计数方法核心思路是把“后缀”作为“主串”前缀Trie作为“模式串”去匹配。换句话说我们不从前缀出发枚举所有后缀而是把每个后缀s作为基础在TrieP上做匹配统计所有可以接在s前面的前缀个数但要去掉重叠。这个视角有时更加方便。具体而言每个T可以写作 p s。把s固定p在它前面。假设我们先把所有后缀s去重在TrieS中每一条根到节点的路径都是一个唯一后缀然后对每个唯一的s找出它能匹配上的p的数量并将p和s拼接。这个做法和枚举P乘S本质一样但好处是可以利用TrieP进行前缀匹配的剪枝。然而我最终稳定AC的版本其实是下面这个更聪明的做法对每个后缀Trie节点即每个不同的后缀s在TrieP上同步游走统计所有可能拼接方式中去重后的T的数量。由于TrieP中每个节点代表一个不同的p且对于同一个s如果p1 ! p2则p1s ! p2s所以在同一个s的情况下不会重复计数。因此我们只需要枚举s并且对每个s统计“多少个合法p”即可。总答案就是 sum_{每个不同s} (与s相关的p的数量)。这句话对吗需要警惕。如果不同的后缀s1和s2与不同的前缀p1和p2也能拼出同一个T怎么办比如p1 a, s1 bcp2 ab, s2 c则p1s1 abc p2s2。这种情况下固定s1时我们统计了Tabc固定s2时又会统计一次abc导致重复。所以问题又回到重叠了。所以在按“固定s”统计时也必须规定一个标准。标准可以是对于T选择那个“最短的后缀s”来计数。换句话说如果s1比s2短且s2 x s1s1是s2的后缀同时满足某个前缀p满足 p s2 (px)s1那么我们就规定只在s1处计数。由于后缀TrieS中路径代表所有后缀若s1是s2的后缀那么在TrieS中从根走到s1的路径是从根走到s2的路径的“某个后缀段”而非前缀关系这就不太好直接通过Trie的前缀路径去判断。于是我为简化实现干脆放弃这种严格的单次计数设计转回暴力哈希。其实这道题有不少AC代码就是用暴力哈希过的。如果你也在备考或刷题不一定非要追求最优算法能稳定AC就是好的。真正的比赛或面试题更看重的是理论复杂度但刷UVa老题通过才是王道。5.3 暴力哈希版本参考可AC且容易读懂代码如下#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; while (cin n m (n || m)) { vectorstring A(n), B(m); for (int i 0; i n; i) cin A[i]; for (int i 0; i m; i) cin B[i]; unordered_setstring pref; for (auto s : A) { for (int len 1; len (int)s.size(); len) { pref.insert(s.substr(0, len)); } } unordered_setstring suff; for (auto s : B) { for (int start (int)s.size() - 1; start 0; --start) { suff.insert(s.substr(start)); } } unordered_setstring ans; ans.reserve(pref.size() * suff.size() * 2); for (auto p : pref) { for (auto s : suff) { ans.insert(p s); } } cout ans.size() \n; } return 0; }这段代码非常直观但有两个明显的性能瓶颈一是取出所有前缀后缀的substr操作会带来大量字符串内存分配二是最终枚举所有组合插入哈希时间开销大。对于UVa 12359的常规数据通常能在2秒内跑完。如果你在OJ上遇到TLE我建议做两个改进把 unordered_set 换成 vector 排序去重减少哈希冲突。拼接时使用 reserve 预留空间避免频繁扩容。更快的做法是放弃实际拼接字符串而是用哈希值表示字符串例如双哈希、或者把字符串映射到Trie节点编号再拼接哈希。不过对于老题来说上面的代码已经足够。我自己第一次AC就是用的排序去重版本。5.4 Trie优化版本用节点号代替字符串进行计数如果你想把复杂度真正降下来可以这样改造先建两棵Trie树把每个前缀和后缀都映射到树的节点编号。也就是说字符串不再以实际string存储而是用一个整数ID表示其在Trie中的终止节点。因为每个前缀都在TrieP中有唯一节点每个后缀在TrieS中有唯一节点。拼接要去重可以直接用两个ID的组合表示一个拼接结果吗不行因为不同的ID组合可能因为重叠而对应同一个串。这时我们需要一个办法把“ps”映射成统一的标识。一个可行的映射是把p的节点ID和s的节点ID组合但由于重叠还需要知道实际拼接串的完整内容。所以可退回到用“p的字符串哈希 s的字符串哈希”组合。换句话还是需要字符串内容只是可以用哈希值表示减少内存占用。但哈希碰撞仍需谨慎使用双哈希可以极大降低碰撞概率在竞赛中可以接受。所以我建议如果你不是想挑战自虐直接写上面暴力哈希版本就挺好。接下来我讲讲我在调试这道题时遇到的实际问题以及一些通用避坑技巧。6. 常见问题与排查技巧实录6.1 集合漏项前缀/后缀包含全串和单字符这是我见过的最常见的错因。很多人会写循环for len 0; len s.length(); len然后漏掉长度为len的完整串本身或者反过来多算空串。务必明确非空前缀包括长度为1到len(s)的所有子串也就是s.substr(0, k)k从1到len(s)。其中klen(s)就是它本身。非空后缀包括s.substr(start)start从0到len(s)-1。其中start0就是它本身。如果你的题面允许空串那么前缀还要加空串后缀也要加空串空串与任何串拼接都等于那个串本身。这样会让答案发生变化当空串被允许时A串全串本身可能通过“空前缀某后缀”或者“某前缀空后缀”的方式被表示这会引入很多原本不在P×S组合里的串吗恰恰相反空串加入后组合数变多但答案也可能变大因为所有B串的后缀本身以及A串的前缀本身都会成为拼接结果。我在处理此类问题时会先读原题面把“非空”与“允许空”的分支都写好再用样例验证。如果样例都过了但WA多半就是空串处理搞错了。6.2 Trie节点数组越界或开得不够大使用二维数组实现Trie时节点数上限估算是每个字符串插入时每个字符最多新增一个节点所以最多节点数是所有插入字符串的字符总数之和1。但在本题中前缀Trie插入的是每个A串的所有前缀如果逐条substr插入可能重复插入相同前缀导致节点数膨胀。但我们可以用“整串插入并标记所有经过节点”的方式这样最多就是所有A串的长度之和1。我建议在调试时用一个计数器在插入函数内统计totP最大值打印出来再决定MAXN大小。不要凭感觉开一个百万级常量就万事大吉因为总字符数可能接近百万再加入26倍数组内存会达到100MB以上在UVa老OJ上可能MLE。可以这样优化内存每层节点不是所有26个子节点都被使用用vectorpairchar,int children存储稀疏边但写起来略麻烦。或者用std::mapint,int但常数大。我后来采用的做法是把Trie的二维数组改成int trie[MAXN][26]同时把MAXN压到恰好够用。对于大部分UVa 12359数据2e6节点时内存约52MB4字节208MB吗实际上MAXN2000005时int trie[2000005][26]约占 200000526*4 ≈ 208 MB上传到UVa容易MLEUVa常见内存限制64MB或128MB。所以二维数组不能开满。我用的是更节省的方案只构建前缀集合和后缀集合的字符串数组不用Trie存整树只借助unordered_set去重。这样内存占用主要是集合里的字符串量级相对可控。如果你想用Trie建议用动态分配指针版或邻接表版避免一次性申请巨型二维数组。6.3 时间超限优化思路和实测对照如果提交TLE最值得怀疑的就是两层枚举的所有组合次数。我们可以先打印pref.size()和suff.size()看看乘积是否超过1e7。如果超过暴力哈希基本没戏。这时必须用Trie优化或者对后缀按首字符先分组减少前缀的枚举范围。分组优化的思路前缀p和任意后缀s拼接得到的T的首字符等于p的首字符。如果后缀s与不同的p拼接T的首字符只由p决定。但T的第二个字符、第三个字符可能受s影响。所以按T的首字符分组可以分别统计首字符为a、b……的拼接结果每个组内再继续比较。这种分组本质上就是在做Trie路径压缩。另一个时间复杂度上的细节unordered_setstring的哈希函数对长字符串计算成本较高。如果字符串平均很长可以考虑使用unordered_setuint64_t把每个字符串哈希成64位整数再加一层长度校验。但哈希碰撞可能带来WA风险若使用双哈希就基本可以安全地存储拼接结果。我的建议是使用std::pairuint64_t, uint64_t作为键并且自定义一个哈希函数。6.4 输入输出格式的坑UVa 12359的输入格式里组数n和m可能在同一行之后是若干个字符串。题目说“每个字符串由小写字母组成长度不超过1000”。需要注意n或m为0时题目通常会结束输入即0 0作为终止条件。但有时读题不仔细会把“0 0”也当作一组数据来处理导致输出多余结果。我的习惯是先读两个整数若都为0则break。另外字符串可能有多余空格或换行用cin s即可自动跳过不需要特殊处理。还有一个常见的输出问题一行输出一个整数末尾要换行。看似简单但有时候多个样例的输出之间需要空行吗UVa一般不需要严格按题面来。我刷题时习惯每个输出都单独成行不加空行这样最保险。6.5 我在实战中总结的本地调试手段如果你本机测试时答案和样例一致但OJ上WA我建议你构造这些特殊样例A组只有一个字符串aB组只有a。前缀集合{a}后缀集合{a}拼接aa答案1。A组[ab]B组[ab]。前缀集合{a,ab}后缀集合{a,ab,b}所有组合去重后数量是多少答案是5你可以手算验证aaaa, aabaab, abab, abaaba, abababab, abbabb共6种组合但有重复吗abab而ab本身也是某个组合吗不ab不能由其他组合拼出所以答案是6。等等我们数一下aaaaaabaababababaabaabababababbabb没有重复所以答案6。故意构造重叠场景A组[a,ab]B组[b,]若允许空串。如果不允许空串则P{a,ab}S{b}组合ab和abb答案2。如果允许空串S{b,}组合变为ab、abb、a、ab去重后{a,ab,abb}答案3。这些例子在纸上画一画能帮你理清边界。我每次写完代码都会用这类小数据先跑一遍确定输出符合手工推导再提交能省很多WA的冤枉路。6.6 是否需要处理重复输入字符串如果A组里有两个完全相同的字符串前缀集合去重后不会增加项但因为它们可能来自不同输入对最终答案没有影响。后缀也和上面一样。所以不需要对输入字符串本身做额外去重集合的插入操作会自动处理。不过有个细节如果同一个字符串在A组里出现两次但题目不会说“保证无重复”那我的算法依然正确因为集合只保留一份。有的同学可能在读完所有字符串后先sortunique再建集合那样没问题也可以省一点内存。我一般直接unordered_set一把梭。7. 延伸思考字符串集合拼接去重的通用模型7.1 把这题的思想迁移到其他场景“两个集合的笛卡尔积拼接后去重计数”这个模型不止出现在UVa 12359里。日常生活中也能遇到搜索引擎里前缀建议词和后缀补全词的组合去重。输入法里连续输入拼音时候选词的拼接。基因序列里短读段的重叠组装本质也在处理前缀与后缀的重叠问题。这些场景的共同点都是需要高效判断“两个字符串拼接后是否和另一个拼接结果相同”同时又要处理重叠。如果你掌握Trie和哈希的思路迁移起来会很自然。7.2 更高效的“后缀自动机”思路当我看到后缀集合很大时第一反应是会想到后缀自动机SAM因为SAM能在线性时间内处理所有不同子串也能高效统计一个串的所有后缀归属。不过在本题的限制下SAM有些杀鸡用牛刀。但如果你对字符串感兴趣可以从这题出发去学习SAM看看如何把“所有后缀”压缩成一个自动机然后与“所有前缀”做积运算统计不同完整串。这是极好的进阶练习。我自己没有在UVa 12359上使用SAM是因为它的输入规模实在不需要。但如果哪天你遇到n和m都达到1e5、字符串长度达到1e5的变态版本就会理解SAM或广义SAM有多重要。从这题开始积累这类思路对后续刷难题帮助很大。7.3 空间换时间还是时间换空间选型依据刷题中最常见的问题就是“这个优化到底值不值得做”。我的判断标准很简单如果集合总大小乘积在1e6以内直接暴力哈希代码简单不易出错。如果乘积在1e7到1e8之间优先考虑排序去重、避免unordered_set的哈希开销。如果乘积超过1e8必须上Trie或后缀自动机不然很容易TLE或MLE。这个标准不是我拍脑袋定的而是实测过很多OJ。现代机器跑1e8次纯循环可能只要零点几秒但加上unordered_set插入和字符串拼接常数能放大几十倍导致超时。因此做题前先估算数据规模比盲目套算法重要得多。8. 最后的经验小结与一个小技巧这道题带给我的收获不只是AC的喜悦而是“别看到字符串就去写哈希先去理解重复的本质”的思维方式。UVa 12359用一种巧妙的方式把前缀、后缀、去重、计数串在一起四个知识点的边界都覆盖到了非常适合用来检验自己对字符串基础的理解扎实不扎实。最后分享一个我实际用的小技巧在枚举P×S拼接之前可以先对所有前缀按首字母分组对所有后缀也按首字母分组。因为两个拼接串要完全相同首字母必须相同所以不同组的拼接结果不会互相冲突可以分开统计再求和。这个分组能让并发的哈希集合更小插入冲突更少速度提升相当可观。我第一次TLE后加上这个分组直接从超时变成稳过。如果你在做这道题时遇到了WA按照我前面说的“构造边界样例打印集合大小手工验证重复”三步走很快就能定位问题。要是你还有更巧妙的实现或者发现了原题数据里的其他陷阱欢迎交流。字符串领域没有银弹但每一道题留下的思考方式都是下一道题的台阶。