其实主要是想学一下字典树的写法，但这个题目又涉及到了DP；
这个题目要求某些单词组成一个长子串的各种组合总数，数据量大，单纯枚举复杂度高，首先肯定是要把各个单词给建成字典树，但是之后该怎么推一时没想到。
其实就是通过递推，从1扫到最后一位，由d[i]代表1-i位的时候的组合总数，则对d[i]进行扩张，凡是可以从第i+1位到第j位正好对应一个单词，则，d[j]+=d[i];
这样递推完，d[len]即为最后结果
为了表示某个单词的结尾，在字典树中再加一个变量
flag，当单词结尾的时候为1，否则为0，这样只要在树种读到了flag=1的时候，即表示读到这个单词。
#include <iostream> #include <cstdio> #include <cstring> using namespace std; struct node { node* ch[27]; bool flag; } tree[500000]; int cnt,len,d[300010]; const int MOD=20071027; node* creat() { node*p; p=&tree[cnt++]; for (int i=0; i<27; i++) p->ch[i]=NULL; p->flag=false; return p; } char s[300010]; char tmp[110]; int ok[300010]; int num; void insertn(node* root,char*s1) { node* p=root; int i=0; while (s1[i]) { int k=s1[i++]-‘a‘; if (p->ch[k]==NULL) { p->ch[k]=creat(); } p=p->ch[k]; } p->flag=true; } void chk(int add,int jmp,node* root) { node* p=root; for (int i=jmp;i<=len;i++) { if (p->ch[s[i]-‘a‘]!=NULL) { p=p->ch[s[i]-‘a‘]; if (p->flag) { d[i]=(d[i]+add)%MOD; ok[i]=1; } } else break; } } int main() { int kase=0; while (scanf("%s",s+1)!=EOF) { cnt=0; scanf("%d",&num); node* root=creat(); for (int i=0; i<num; i++) { scanf("%s",tmp); //puts(tmp); insertn(root,tmp); } len=strlen(s+1); //cout<<len<<endl; memset(d,0,sizeof d); memset(ok,0,sizeof ok); d[0]=1; ok[0]=1; for (int i=1;i<=len;i++) { if (ok[i-1]) chk(d[i-1],i,root); } printf("Case %d: %d\n",++kase,d[len]); } return 0; }
UVALive 3942 字典树+dp,布布扣,bubuko.com
原文：http://www.cnblogs.com/kkrisen/p/3597403.html