给一个串和一个字典(一些字符串)
将这个串分解为字典单词的连接(如 abcd = ab+cd =a+bcd )
问有多少方案
线性dp
枚举位置 i
f[i] += f[j] i<j , string(i,j) 为字典单词
直接枚举 j 和单词 明显超时
用到字典树,从 位置 i 开始在字典树上找单词,找到后更新 f[i]
#include <iostream> #include <cstring> #include <vector> using namespace std; #define mod 20071027 const int N=5e5; int n; int tot,ch[N][30],val[N]; char str[N],tmp[N]; int f[N],L[N]; void insert(char *s,int v){ int i,u=1,l=strlen(s); for(i=0;i<l;i++){ int c=s[i]-'a'; if(ch[u][c]==0){ ++tot; memset(ch[tot],0,sizeof ch[tot]); ch[u][c]=tot; val[tot]=0; } u=ch[u][c]; } val[u]=v; } void find(char *s,int len,int id){ int i,u=1; for(i=0;i<len;i++){ if(s[i]=='\0') break; int c=s[i]-'a'; if(ch[u][c]==0) break; u=ch[u][c]; if(val[u]!=0) f[id]+=f[id+L[val[u]]],f[id]%=mod; } } int main(){ // int i,j,cas=0; while(cin>>str>>n){ memset(f,0,sizeof f); tot=1; memset(ch[1],0,sizeof ch[1]); for(i=1;i<=n;i++){ cin>>tmp; insert(tmp,i); L[i]=strlen(tmp); } int l=strlen(str); f[l]=1; for(i=l-1;i>=0;i--){ find(str+i,l-i,i); } printf("Case %d: %d\n",++cas,f[0]); } }
原文地址:http://www.cnblogs.com/towboa/p/16833285.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性