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代码:

 #include<cstdio>
#include<cstring> #define STR 300000 + 10//模板串的长度
#define SIZE 400000 //字典树的节点数
#define LETTER 26 //字符个数
#define S 100+10//单词的长度
#define MOD 20071027 int size, trie[SIZE][LETTER];//size字典的节点数 trie字典树的节点
bool val[SIZE];//记录字典树的节点是否为单词
char strp[STR];//模板单词
int dp[STR];//dp[i]表示从0~i有多少种组成模板单词 void init(int x){//初始化节点
val[x] = ;
memset(trie[x], , sizeof(trie[x]));
} int idx(char c){
return c - 'a';
} void insert(char str[]){
int u = ;
for(int i = ; str[i]; ++i){
int num = idx(str[i]);
if(!trie[u][num]){//儿子为空
init(size);//扩充节点
trie[u][num] = size++;
}
u = trie[u][num];//指向下一个节点
}
val[u] = true;//当前节点是一个单词的末尾
} void dynamic(int cs){
memset(dp, , sizeof(dp));
dp[] = ;
int i;
for(i = ; strp[i]; ++i){
int u = ;
for(int j = i; strp[j]; ++j){
int num = idx(strp[j]);
if(!trie[u][num]){
break;
}
u = trie[u][num];
if(val[u]){
dp[j + ] = (dp[j + ] + dp[i]) % MOD;//dp公式
}
}
}
printf("Case %d: %d\n", cs, dp[i]);
} int main(){
int s;
char str[S];
for(int cs = ; ~scanf("%s", strp); ++cs){ init();//初始化节字典树
size = ; scanf("%d", &s);
while(s--){
scanf("%s", str);
insert(str);
}
dynamic(cs);
}
return ;
}
上一篇:C++ char*,const char*,string,int 的相互转换


下一篇:Eclipse开发C++遇到的Binary not found等问题