UVa 1113 Multiple Morse Matches

题目描述在莫尔斯电码中字母被编码为点.和划-的序列。当字母之间没有停顿的时候一段莫尔斯电码可能有多种解释。例如----可以被解释为CAT或NXT等。给定一个莫尔斯码字符串只包含.和-长度不超过100010001000和一个词典包含NNN个单词N≤10000N \leq 10000N≤10000要求计算将整个莫尔斯码字符串完全分割成词典中的单词每个单词必须完全匹配的不同短语的数量。结果保证不超过2×1092 \times 10^92×109。输入的第一行是测试用例的数量TTT每个测试用例包含一个莫尔斯字符串、单词数量NNN和NNN个单词。输出每个测试用例的短语数量相邻用例的输出之间有一个空行。题目分析本题的关键在于莫尔斯码没有分隔符因此同一个莫尔斯序列可能对应多种单词分割方式。核心难点词典中的单词需要通过字母到莫尔斯码的映射先转换成莫尔斯码串。需要在莫尔斯码字符串上进行动态规划快速判断从某个位置开始能否匹配某个单词的莫尔斯码。词典单词数量最多100001000010000莫尔斯串长度最多100010001000直接对每个位置遍历所有单词进行匹配会导致O(L⋅N⋅wordLen)O(L \cdot N \cdot wordLen)O(L⋅N⋅wordLen)超时。关键观察单词的莫尔斯码长度不一但总长度有限。可以将词典中所有单词的莫尔斯码构建成Trie\texttt{Trie}Trie树前缀树这样在莫尔斯码串上从某个位置开始匹配时只需沿着Trie\texttt{Trie}Trie向下遍历O(L⋅avgMatchLen)O(L \cdot avgMatchLen)O(L⋅avgMatchLen)即可找到所有可能的匹配长度。这样每个位置iii的匹配过程是沿着Trie\texttt{Trie}Trie前进直到无法匹配或到达叶节点复杂度大幅降低。解题思路1. 预处理字母到莫尔斯码的映射定义数组morseMap[26]将A到Z映射为对应的莫尔斯码用.和-表示。2. 词典预处理对于词典中的每个单词通过映射将其转换为莫尔斯码串。然后将所有单词的莫尔斯码插入到Trie\texttt{Trie}Trie树中。在Trie\texttt{Trie}Trie树的每个节点上使用一个vectorint存储以该节点结尾的单词的莫尔斯码长度因为可能有多个不同单词对应相同的莫尔斯码如AT和T可能产生相同莫尔斯码但通常不会这里仍保存长度。3. 动态规划状态定义设dp[i]dp[i]dp[i]表示莫尔斯码字符串的前iii个字符可以解析成的不同短语的数量。初始化dp[0]1dp[0] 1dp[0]1空串可以解析为空短语。目标dp[L]dp[L]dp[L]其中LLL是莫尔斯码字符串的长度。4. 状态转移对于每个位置iii0≤iL0 \le i L0≤iL如果dp[i]0dp[i] 0dp[i]0则从Trie\texttt{Trie}Trie的根节点出发尝试从莫尔斯字符串的第iii个字符开始向后匹配设jjj从iii开始依次取字符morse[j]。如果当前Trie\texttt{Trie}Trie节点存在对应的子节点则移动到子节点否则匹配失败跳出循环。如果当前Trie\texttt{Trie}Trie节点存储了单词长度即wordLengths非空则对于每一个长度wlenwlenwlen有dp[iwlen]dp[i] dp[i wlen] \mathrel{} dp[i]dp[iwlen]dp[i]注意iwleni wleniwlen必须不超过LLL。这样每个位置iii的匹配是沿着Trie\texttt{Trie}Trie一次遍历完成的时间复杂度为O(L⋅O(L \cdotO(L⋅平均匹配深度)))而平均匹配深度不超过最长莫尔斯码的长度每个字母平均2 42~424个符号单词长度有限。5. 复杂度分析构建Trie\texttt{Trie}TrieO(∑wordMorseLen)O(\sum wordMorseLen)O(∑wordMorseLen)每个单词长度不超过莫尔斯串总长度。动态规划每个iii最多沿 Trie 走O(L)O(L)O(L)步但实际因为莫尔斯码字符串长度限制和 Trie 深度限制总复杂度约为O(L⋅maxMorseWordLen)O(L \cdot maxMorseWordLen)O(L⋅maxMorseWordLen)满足要求。6. 结果范围题目保证结果≤2×109\le 2 \times 10^9≤2×109因此使用int即可。但为防中间累加溢出可以使用long long最后转int或直接使用int因为加和不会超过2×1092 \times 10^92×109。代码实现// Multiple Morse Matches// UVa ID: 1113// Verdict: Accepted// Submission Date: 2026-05-30// UVa Run Time: 0.110s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 字母到莫尔斯码的映射conststring morseMap[26]{.-,-...,-.-.,-..,.,..-.,--.,....,..,.---,-.-,.-..,--,-.,---,.--.,--.-,.-.,...,-,..-,...-,.--,-..-,-.--,--..};// 将单词转换为莫尔斯码stringwordToMorse(conststringword){string res;for(charc:word)resmorseMap[c-A];returnres;}// Trie 树节点structTrieNode{unordered_mapchar,TrieNode*children;vectorintwordLengths;// 存储以当前节点结尾的单词的莫尔斯码长度TrieNode(){}};// 向 Trie 中插入莫尔斯码单词voidinsertTrie(TrieNode*root,conststringmorse,intlen){TrieNode*noderoot;for(charc:morse){if(!node-children.count(c))node-children[c]newTrieNode();nodenode-children[c];}node-wordLengths.push_back(len);}intmain(){ios::sync_with_stdio(false);cin.tie(0);intT;cinT;for(intcaseNum0;caseNumT;caseNum){if(caseNum0)cout\n;// 用例之间空行string morse;cinmorse;// 莫尔斯码字符串连续无空格intN;cinN;// 构建 Trie 树TrieNode*rootnewTrieNode();for(inti0;iN;i){string word;cinword;string morseWordwordToMorse(word);insertTrie(root,morseWord,(int)morseWord.length());}intlen(int)morse.length();vectorlonglongdp(len1,0);dp[0]1;// 动态规划for(inti0;ilen;i){if(dp[i]0)continue;TrieNode*noderoot;// 从位置 i 开始向后匹配for(intji;jlen;j){charcmorse[j];if(!node-children.count(c))break;nodenode-children[c];// 检查是否有单词在此结束for(intwlen:node-wordLengths){if(iwlenlen){dp[iwlen]dp[i];}}}}coutdp[len]\n;// 释放 Trie 内存为简洁起见省略实际竞赛中可接受}return0;}