首页 > 代码库 > LA 3942 - Remember the Word （字典树 + dp）
LA 3942 - Remember the Word （字典树 + dp）
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1943
题目大意：
给定一个字符串和给定一个单词集合。问从给定单词集合中选取单词，有多少种选取方法刚好拼接成字符串。
例如:
abcd
4
a
b
cd
ab
有两种
a-b-cd
ab-cd
这两种情况
解题思路：
因为给定的字符串的长度是3*10^5所以暴力就不能解决问题了。
dp[j + 1] = dp[j + 1] + dp[i];dp[j + 1]表示从S[0~j]有多少中组成方法 ，用公式的条件是S[i~j]是单词集合里的元素
有了上面的dp，时间减少了，但是每次查找单词如果枚举每个单词，则时间复杂度3*10^5*4*10^3*10^2。我们用字典树
存储所有单词。每次查找单词时间最坏是O(10^2)。
所以总时间复杂度是O（n*10^2）。
参开资料《算法入门经典训练之南》刘汝佳 P209
AC代码：
1 #include<cstdio> 2 #include<cstring> 3 4 #define STR 300000 + 10//模板串的长度 5 #define SIZE 400000 //字典树的节点数 6 #define LETTER 26 //字符个数 7 #define S 100+10//单词的长度 8 #define MOD 20071027 9 10 int size, trie[SIZE][LETTER];//size字典的节点数 trie字典树的节点11 bool val[SIZE];//记录字典树的节点是否为单词12 char strp[STR];//模板单词13 int dp[STR];//dp[i]表示从0~i有多少种组成模板单词14 15 void init(int x){//初始化节点16 val[x] = 0;17 memset(trie[x], 0, sizeof(trie[x]));18 }19 20 int idx(char c){21 return c - ‘a‘;22 }23 24 void insert(char str[]){25 int u = 0;26 for(int i = 0; str[i]; ++i){27 int num = idx(str[i]);28 if(!trie[u][num]){//儿子为空 29 init(size);//扩充节点30 trie[u][num] = size++;31 }32 u = trie[u][num];//指向下一个节点33 }34 val[u] = true;//当前节点是一个单词的末尾35 }36 37 void dynamic(int cs){38 memset(dp, 0, sizeof(dp));39 dp[0] = 1;40 int i;41 for(i = 0; strp[i]; ++i){42 int u = 0;43 for(int j = i; strp[j]; ++j){44 int num = idx(strp[j]);45 if(!trie[u][num]){46 break;47 }48 u = trie[u][num];49 if(val[u]){50 dp[j + 1] = (dp[j + 1] + dp[i]) % MOD;//dp公式51 }52 }53 }54 printf("Case %d: %d\n", cs, dp[i]);55 }56 57 int main(){58 int s;59 char str[S];60 for(int cs = 1; ~scanf("%s", strp); ++cs){61 62 init(0);//初始化节字典树63 size = 1;64 65 scanf("%d", &s);66 while(s--){67 scanf("%s", str);68 insert(str);69 }70 dynamic(cs);71 }72 return 0;73 }
LA 3942 - Remember the Word （字典树 + dp）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。