题目描述给定一个长度不超过300,000300,000300,000的字符串SSS以及一个包含SSS个单词的字典1≤S≤40001 \leq S \leq 40001≤S≤4000每个单词长度不超过100100100全部为小写字母且无重复单词。要求计算将字符串SSS划分成若干段的方式数其中每一段都必须是字典中的某个单词。由于结果可能很大输出对200710272007102720071027取模后的值。输入包含多个测试用例每个测试用例之间用一个空行分隔。对于每个测试用例首先给出目标字符串然后是字典大小SSS接着是SSS个字典单词。题目分析问题本质这是一个字符串划分计数问题类似于经典的单词拆分问题但需要计算所有可能的划分方式数目。样例分析考虑样例abcd 4 a b cd ab可能的划分方式有abcdabcd因此答案为222。直接思路与复杂度分析我们可以使用动态规划来解决这个问题定义dp[i]dp[i]dp[i]表示字符串前iii个字符的划分方式数。初始状态dp[0]1dp[0] 1dp[0]1空串有一种划分方式。状态转移对于每个位置iii枚举字典中的每个单词www如果substr(i−len1,len)wsubstr(i - len 1, len) wsubstr(i−len1,len)w则dp[i]dp[i−len] dp[i] dp[i - len]dp[i]dp[i−len]最终答案dp[n]dp[n]dp[n]其中nnn是字符串长度。然而直接实现的时间复杂度为O(n×S×L)O(n \times S \times L)O(n×S×L)其中n≤300,000n \leq 300,000n≤300,000S≤4000S \leq 4000S≤4000L≤100L \leq 100L≤100这显然会超时。优化策略我们需要优化匹配过程。注意到字典单词长度不超过100100100我们可以使用Trie\texttt{Trie}Trie树来高效匹配所有可能的单词优化后的思路将字典中所有单词插入Trie\texttt{Trie}Trie树在Trie\texttt{Trie}Trie节点中记录以该节点结尾的单词长度对于字符串的每个位置iii在Trie\texttt{Trie}Trie中最多向下匹配100100100个字符遇到单词结尾时根据单词长度进行状态转移这样时间复杂度降为O(n×100)O(n \times 100)O(n×100)可以接受。算法设计数据结构Trie\texttt{Trie}Trie节点子节点指针数组大小为262626对应小写字母存储以该节点结尾的单词长度列表动态规划状态dp[i]dp[i]dp[i]前iii个字符的划分方式数初始状态dp[0]1dp[0] 1dp[0]1最终答案dp[n]dp[n]dp[n]算法流程构建Trie\texttt{Trie}Trie树插入所有字典单词初始化dpdpdp数组对于每个位置iii0≤in0 \leq i n0≤in从根节点开始对于jij iji到i99i99i99不超过n−1n-1n−1沿Trie\texttt{Trie}Trie树向下移动如果遇到单词结尾更新dp[ilen]dp[i len]dp[ilen]输出dp[n]dp[n]dp[n]清理Trie\texttt{Trie}Trie树内存代码实现// Remember the Word// UVa ID: 1401// Verdict: Accepted// Submission Date: 2025-10-16// UVa Run Time: 0.100s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includeiostream#includecstring#includevector#includestringusingnamespacestd;constintMOD20071027;// 取模值constintMAXN300010;// 最大字符串长度constintALPHABET26;// 字母表大小intdp[MAXN];// dp数组// Trie树节点结构structTrieNode{TrieNode*children[ALPHABET];// 子节点指针数组vectorintwordLengths;// 存储以此节点结尾的单词长度TrieNode(){memset(children,0,sizeof(children));// 初始化子节点为空}};// 向Trie树中插入单词voidinsert(TrieNode*root,conststringword){TrieNode*noderoot;for(charch:word){intidxch-a;// 计算字母索引if(!node-children[idx]){node-children[idx]newTrieNode();// 创建新节点}nodenode-children[idx];}node-wordLengths.push_back(word.length());// 记录单词长度}// 递归清理Trie树内存voidclearTrie(TrieNode*root){if(!root)return;for(inti0;iALPHABET;i){clearTrie(root-children[i]);// 递归清理子节点}deleteroot;// 删除当前节点}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string text;intcaseNum1;while(cintext){// 读取每个测试用例的目标字符串intS;cinS;// 读取字典大小TrieNode*rootnewTrieNode();// 创建Trie根节点// 插入所有字典单词for(inti0;iS;i){string word;cinword;insert(root,word);}intntext.length();memset(dp,0,sizeof(dp));// 初始化dp数组dp[0]1;// 空串有1种划分方式// 动态规划过程for(inti0;in;i){if(dp[i]0)continue;// 如果当前位置不可达跳过TrieNode*noderoot;// 从位置i开始在Trie中最多匹配100个字符for(intji;jnj-i100;j){intidxtext[j]-a;if(!node-children[idx])break;// 无匹配退出nodenode-children[idx];// 遍历所有以当前节点结尾的单词for(intlen:node-wordLengths){if(ilenn){dp[ilen](dp[ilen]dp[i])%MOD;// 状态转移}}}}coutCase caseNum: dp[n]\n;// 输出结果clearTrie(root);// 清理Trie树内存}return0;}复杂度分析时间复杂度O(n×100)O(n \times 100)O(n×100)其中nnn是目标字符串长度。每个位置最多匹配100100100个字符。空间复杂度O(字典总字符数n)O(\text{字典总字符数} n)O(字典总字符数n)主要用于存储Trie\texttt{Trie}Trie树和dp\texttt{dp}dp数组。总结本题通过结合Trie\texttt{Trie}Trie树和动态规划高效地解决了大规模字符串划分计数问题。关键点在于利用Trie\texttt{Trie}Trie树优化单词匹配过程将复杂度从不可接受的O(n×S×L)O(n \times S \times L)O(n×S×L)降低到可行的O(n×100)O(n \times 100)O(n×100)。这种Trie\texttt{Trie}TrieDP\texttt{DP}DP的思路在字符串处理问题中非常实用。