UVa 1401 Remember the Word-拓冰建站

题目描述

给定一个长度不超过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

可能的划分方式有：

abcd
abcd

因此答案为222。

直接思路与复杂度分析

我们可以使用动态规划来解决这个问题：

定义dp[i]dp[i]dp[i]表示字符串前iii个字符的划分方式数。
初始状态：dp[0]=1dp[0] = 1dp[0]=1（空串有一种划分方式）。
状态转移：对于每个位置iii，枚举字典中的每个单词www，如果substr(i−len+1,len)==wsubstr(i - len + 1, len) == wsubstr(i−len+1,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,000，S≤4000S \leq 4000S≤4000，L≤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数组
对于每个位置iii（0≤i<n0 \leq i < n0≤i<n）：
- 从根节点开始
- 对于j=ij = ij=i到i+99i+99i+99（不超过n−1n-1n−1）：
  - 沿Trie\texttt{Trie}Trie树向下移动
  - 如果遇到单词结尾，更新dp[i+len]dp[i + len]dp[i+len]
输出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//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<iostream>#include<cstring>#include<vector>#include<string>usingnamespacestd;constintMOD=20071027;// 取模值constintMAXN=300010;// 最大字符串长度constintALPHABET=26;// 字母表大小intdp[MAXN];// dp数组// Trie树节点结构structTrieNode{TrieNode*children[ALPHABET];// 子节点指针数组vector<int>wordLengths;// 存储以此节点结尾的单词长度TrieNode(){memset(children,0,sizeof(children));// 初始化子节点为空}};// 向Trie树中插入单词voidinsert(TrieNode*root,conststring&word){TrieNode*node=root;for(charch:word){intidx=ch-'a';// 计算字母索引if(!node->children[idx]){node->children[idx]=newTrieNode();// 创建新节点}node=node->children[idx];}node->wordLengths.push_back(word.length());// 记录单词长度}// 递归清理Trie树内存voidclearTrie(TrieNode*root){if(!root)return;for(inti=0;i<ALPHABET;i++){clearTrie(root->children[i]);// 递归清理子节点}deleteroot;// 删除当前节点}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);string text;intcaseNum=1;while(cin>>text){// 读取每个测试用例的目标字符串intS;cin>>S;// 读取字典大小TrieNode*root=newTrieNode();// 创建Trie根节点// 插入所有字典单词for(inti=0;i<S;i++){string word;cin>>word;insert(root,word);}intn=text.length();memset(dp,0,sizeof(dp));// 初始化dp数组dp[0]=1;// 空串有1种划分方式// 动态规划过程for(inti=0;i<n;i++){if(dp[i]==0)continue;// 如果当前位置不可达，跳过TrieNode*node=root;// 从位置i开始，在Trie中最多匹配100个字符for(intj=i;j<n&&j-i<100;j++){intidx=text[j]-'a';if(!node->children[idx])break;// 无匹配，退出node=node->children[idx];// 遍历所有以当前节点结尾的单词for(intlen:node->wordLengths){if(i+len<=n){dp[i+len]=(dp[i+len]+dp[i])%MOD;// 状态转移}}}}cout<<"Case "<<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}Trie+DP\texttt{DP}DP的思路在字符串处理问题中非常实用。