UVALive 3942 Remember the Word

题意：给出一个由S个不同单词组成的字典和一个长字符串。把这个字符串分解成若干个单词的连接（单词可以重复使用），有多少种方法？

Sample Input

abcd

Sample Output

Case 1: 2

思路：利用字典树上的dp，dp[i]表示从i到末尾有多少种方案，大白书字典树的例题，虽然是例题还是看了一会儿orz，我太弱了，注意ch数组要开成最大节点数*26的大小，表示每个节点连的字母是什么，初始节点为0，val也要开成最大节点数的大小，表示该节点是否为单词的最后一个字母。然后就是dp的过程了，从末尾往前，每次循环从i到结尾，如果碰到某个单词的结尾（也就是val[j]==1）就代表该单词可以作为某些组合的一部分，dp[i]+=dp[j+1]，关键部分就是这里了吧。

代码：

#include<iostream>
#include<string.h>
using namespace std;

const int maxn=4001*101;
const int maxm=3e5+5;
const int mod=20071027;

struct Trie{
   int ch[maxn][26];
   int val[maxn];
   int sz;
   Trie(){
       sz=1;
       memset(ch[0],0,sizeof(ch[0]));
   }
   int idx(char c){
       return c-'a';
   }
   void insert(char *s,int v){
       int u=0,l=strlen(s);
       for(int i=0;i<l;i++){
           int x=idx(s[i]);
           if(ch[u][x]==0){
               memset(ch[sz],0,sizeof(ch[sz]));
               val[sz]=0;
               ch[u][x]=sz++;
           }
           u=ch[u][x];
       }
       val[u]=v;
   }
}e;

char s[maxm];
char a[110];
long long dp[maxm];

int main(){
   int t=0;
   while(~scanf("%s",s)){
       int n;
       scanf("%d",&n);
       memset(e.ch[0],0,sizeof(e.ch[0]));
       e.sz=1;
       for(int i=0;i<n;i++){
           scanf("%s",a);
           e.insert(a,1);
       }
       int l=strlen(s);
       memset(dp,0,sizeof(dp));
       dp[l]=1;
       int u;
       for(int i=l-1;i>=0;i--){
           u=0;
           for(int j=i;j<l;j++){
               int x=e.idx(s[j]);
               if(e.ch[u][x]==0)break;
               u=e.ch[u][x];
               if(e.val[u])dp[i]+=dp[j+1];
           }
           dp[i]%=mod;
       }
       //printf("%d ",e.sz);
       //for(int i=0;i<=l;i++)printf("%lld ",dp[i]);
       printf("Case %d: %lld ",++t,dp[0]);
   }
   return 0;
}