首页 > 代码库 > LA ——3942 - Remember the Word(Trie 入门)
LA ——3942 - Remember the Word(Trie 入门)
3942 - Remember the WordRegionals 2007 >> Asia - NanjingTime limit: 3.000 seconds |
——————————————————————————————————————————————————————
从右往左地推,令dp[i] 表示字符串 S[i....len]的分解方案数,则dp[i]=sum(dp[i+len(x)]) ,我们只要枚举 S[i....len]的前缀,在所给的单词中查找前缀,如果存在,则进行状态转移
#include<iostream> #include<cstring> #include<cstdio> #define maxnode 400001 #define sigma_size 26 #define M 300001 #define mod 20071027 using namespace std; char str[M]; int dp[M]; struct Trie { int ch[maxnode][sigma_size]; int val[maxnode]; int sz; void reset(){memset(ch[0],0,sizeof ch[0]);memset(val,0,sizeof val);sz=1;} int idx(char c){return c-'a';} void insert(char *s) { int u=0,l=strlen(s); for(int i=0;i<l;++i){ int c=idx(s[i]); if(!ch[u][c]){ memset(ch[sz],0,sizeof ch[sz]); ch[u][c]=sz++; } u=ch[u][c]; } val[u]=1; } int query(char *s,int p) { int u=0,l=strlen(s),res=0; for(int i=p;i<l;++i){ int c=idx(s[i]); if(!ch[u][c]) return res; u=ch[u][c]; if(val[u]){ res+=dp[i+1]; res%=mod; } } return res; } }T; int main() { char a[110]; int cas=1; while(scanf("%s",str)!=EOF){ memset(dp,0,sizeof dp); int n; T.reset(); scanf("%d",&n); for(int i=0;i<n;++i){ scanf("%s",a); T.insert(a); } int l=strlen(str); dp[l]=1; for(int i=l-1;i>=0;--i){ dp[i]=T.query(str,i); } printf("Case %d: %d\n",cas++,dp[0]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。