首页 > 代码库 > LA 3942 Remember the Word 字典树+dp
LA 3942 Remember the Word 字典树+dp
#include <cstdio>#include <cstring>using namespace std;#define mod 20071027int dic[401000][28],val[401000];char str[301000];int dp[301000];int s,sz;char T[110];void insert(char *ch){ int u=0,len=strlen(ch); for(int i=0;i<len;i++) { int id=ch[i]-‘a‘; if(!dic[u][id]) { memset(dic[sz],0,sizeof(dic[sz])); dic[u][id]=sz++; } u=dic[u][id]; } val[u]=1;}int main(){ int sum=0; while(scanf("%s",str)!=EOF) { sum++; memset(val,0,sizeof(val)); sz=1; memset(dic[0],0,sizeof(dic[0])); memset(dp,0,sizeof(dp)); scanf("%d",&s); for(int i=0;i<s;i++) { scanf("%s",T); insert(T); } int len=strlen(str); dp[len]=1; for(int i=len-1;i>=0;i--) { int u=0; int tot=0; for(int j=i;j<len;j++) { tot++; int id=str[j]-‘a‘; if(!dic[u][id]) break; u=dic[u][id]; if(val[u]) dp[i]=(dp[i]+dp[i+tot])%mod; } } //for(int i=0;i<=len;i++) printf("%d ",dp[i]); printf("Case %d: %d\n",sum,dp[0]); } return 0;}
LA 3942 Remember the Word 字典树+dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。