首页 > 代码库 > LA3942 Remember the Word(Trie+DP)
LA3942 Remember the Word(Trie+DP)
Trie图的简单应用。这题关键是想出递推式。令d(i)表示从字符i开始的字符串,d(i)=sum{d(i+len(x))},x是s[i...L]的前缀。然后把所有可分解成的单词构造成一颗Trie树,再让母串在上面跑,d[0]即是方案总数。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define mod 20071027 #define M 400005 using namespace std; int n,top,len; int tree[M][27]; char S[M]; char p[105]; int val[M]; int d[M]; void init() { top=1; memset(tree,0,sizeof(tree)); memset(d,0,sizeof(d)); } int idx(char c) { return c-'a'; } void insert(char *s) { int Len=strlen(s); int u=0; for(int i=0;i<Len;i++) { int c=idx(s[i]); if(!tree[u][c]) { val[top]=0; tree[u][c]=top++; } u=tree[u][c]; } val[u]=1; } int query(char *s,int start) { int count=0; int u=0; for(int i=start;i<len;i++) { int c=idx(s[i]); u=tree[u][c]; if(!u) return count; if(val[u]) { count+=d[i+1]; count%=mod; } } return count; } int main() { int t=1; //freopen("d:\\test.txt","r",stdin); while(scanf("%s",S)!=EOF) { scanf("%d",&n); init(); for(int i=0;i<n;i++) { scanf("%s",p); insert(p); } len=strlen(S); d[len]=1; for(int i=1;i<=len;i++) { d[len-i]=query(S,len-i); } cout<<"Case "<<t++<<": "<<d[0]<<endl; } return 0; }
LA3942 Remember the Word(Trie+DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。