首页 > 代码库 > uva 1401 dp+Trie
uva 1401 dp+Trie
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=4147
题意:给定一个字符串,以及若干单词,求有几种方式能用单词组成字符串
我先是dp方程推得有问题不知怎么修改搞得卡了很久,然后就是数组开得太小一直RE
trie数组大小=单词个数*单词长度
dp[i]为以str[i]开头的后缀的ans,dp[i]=segma(dp[k]),其中k表示str[i...k-1]是一个单词,如果k=len,那么dp[i]++;
#include <iostream> #include <cstring> #include <cstdio> using namespace std; #define ll long long const int N =4000*100+100; const int MOD =20071027; char str[300019],pat[115]; ll dp[300019]; const int tk=26,tb='a'; int top,tree[N][tk+1],len; void init() { top=1; memset(tree[0],0,sizeof(tree[0])); } int sear(char*s,int i) { int cnt=0; ll ans=0; for(int rt=0;rt=tree[rt][*s-tb] ;++s) { if(*(s)==0)break; cnt++; if(tree[rt][tk])//cnt!=tree[rt][tk]表示dp[i..len-1]是一个单词,此时没有增加分割的种数 { if(*(s+1)==0)ans++; ans=(ans+dp[i+cnt])%MOD; ////////////////////// //printf("rt=%d s=%s i=%d cnt=%d dp=%lld\n",rt,str+i+cnt,i,cnt,dp[i]); ////////////////////// } } return ans; } void Insert(char*s, int Rank=0)//Rank为长度 { int rt,nxt; for(rt=0;*s;rt=nxt,++s,Rank++) { nxt=tree[rt][*s-tb]; if(0 == nxt)//nxt!=0的时候就是有公共前缀了,已经在之前做过了,只需继续跳转就行he中插入her,到h,e都是nxt!=0不用插入 { tree[rt][*s-tb]=nxt=top; memset(tree[top],0,sizeof(tree[top])); top++; } } tree[rt][tk]=Rank; } int main() { //freopen("uva1401.txt","r",stdin); int n,ncase=1,pos; while(scanf("%s",str)!=EOF) { init(); pos=0; len=strlen(str); scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%s",pat); Insert(pat); } dp[len]=0; for(int i=len-1;i>=0;i--) { dp[i]=0; dp[i]=sear(str+i,i); } printf("Case %d: %lld\n",ncase++,dp[0]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。