已知一些单词，选择其中一些单词组成目的字符串，问共有多少种方法。其实初看到这道题，自然而然地可以想到动态规划中经典的硬币问题：例如，问1元，2元，5元，总共有多少种方法能组成20元？这里不过是把硬币换成了单词而已。但是，如果真的只是像硬币问题一样每个单词都轮询一遍，，显然太慢了，最多要有300000*4000*100次比对。
假如利用trie数的话，至多只要比对100次，就能找到所有匹配的单词。然后将字符串从左至右DP即可。设d[i]表示从位置i开始的后缀的解，已知d[i]~d[n],那么求d[i-1]的话，只要找出能和suffix[i-1….n]的前缀匹配的单词，设单词长度为len，则d[i-1]+=d[i-1+len]即可，将所有匹配的单词找出来即可。
最后，不要忘记一个Case结束之后，要重置trie树。
#include <iostream>#include <cstdio>#include <vector>#include <string>#include <cstring>#define MAX300000+5#define MAXS4000+5#define MAXL100+5#define maxnode4000*100#define sigma_size 26#define MOD20071027using namespace std;struct trie{int ch[maxnode][sigma_size];int val[maxnode];int sz;trie(){sz=1;memset(ch[0],0,sizeof(ch[0]));}int idx(char c) {return c-'a';}void Insert(char*s,int num)//trie树中插入新单词{int u=0,n=strlen(s);for(int i=0;i<n;++i){int c=idx(s[i]);if(!ch[u][c]){memset(ch[sz],0,sizeof(ch[sz]));val[sz]=0;ch[u][c]=sz++;}u=ch[u][c];}val[u]=num;}vector<int> check(char*s){vector<int> ans;int u=0,n=strlen(s);for(int i=0;i<n;++i){int c=idx(s[i]);if(!ch[u][c]){//不匹配则退出return ans;}else{u=ch[u][c];//有匹配的单词则插入相应单词的编号if(val[u]){ ans.push_back(val[u]);}}}return ans;}void reset(){sz=1;memset(ch[0],0,sizeof(ch[0]));}//重置trie树};trie T;int d[MAX],slen[MAX],S,Case;//slen存放相应编号的单词的长度char line[MAX];int main(){while(cin>>line){cin>>S;T.reset();for(int i=1;i<=S;++i){char s[MAXL];cin>>s;slen[i]=strlen(s);T.Insert(s,i);}memset(d,0,sizeof(d));d[strlen(line)]=1;for(int i=strlen(line)-1;i>=0;–i){//从后往前DPvector<int> ans;ans=T.check(line+i);//找出所有匹配的单词的编号for(int j=0;j<ans.size();++j){d[i]=(d[i]+d[i+slen[ans[j]]])%MOD;}}cout<<"Case "<<++Case<<": "<<d[0]<<endl;}return 0;}
你不怕困难，困难就怕你。
