UVALive 3942 Remeber the Word Trie+递推

        很好嘛，一直都是做DP，这种题倒是做的很少了

        想到了是递推，但是没敢写，嘛，多多练习就好

        先把给的所有单词建成一个Trie，把原串记做str

        定义dp[i]表示在str中从1~i(含，且str下标从1开始)的子串的合成方法数，因此答案就是dp[length(str)]

        dp[i]=∑(k∈S)dp[i-k]  ，{ k∈S |  str[i-k.....k]∈ Trie   }  ，用语言表述就是假若str从1~i-k再加上字典里的一段就等于str从1~i的话，此时dp[i]就可以+=这个dp[i-k]

        这个状态转移方程还不是很好写，改成刷表法的话，即：

        dp[i]，∀ k>=i， dp[k]+=dp[i]  iff str[i+1.....k]∈ Trie，这样就好写一些啦

        嘛，第一次写Trie和递推的组合题，有了经验了。

#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int modulu=20071027;int n,sz,ch[400005][26],kcase=1,val[400005],newnode(),root,dp[300010],len;char str[300010]{1},tmp[105];void init(),ins(char* s);int main(){    ios_base::sync_with_stdio(false);    while(cin>>(str+1)){        len=strlen(str+1);        init();        cin>>n;        for(int i=0;i<n;++i){            cin>>tmp;            ins(tmp);        }        for(int i=0,now=root;str[i];++i,now=root){            for(int j=1;str[j+i];++j){                now=ch[now][str[j+i]-'a'];                if(now==root)                    break;                else if(val[now]){                    dp[j+i]+=dp[i];                    dp[j+i]%=modulu;                }            }        }        cout<<"Case "<<kcase++<<": "<<dp[len]<<endl;    }    return 0;}void init(){    sz=0;    root=newnode();    memset(dp,0,sizeof(int)*(len+1));    dp[0]=1;}void ins(char* s){    int now=root;    for(int i=0;s[i];++i){        if(ch[now][s[i]-'a']==root)            ch[now][s[i]-'a']=newnode();        now=ch[now][s[i]-'a'];    }    val[now]=1;}int newnode(){    val[sz]=0;    memset(ch[sz],0,sizeof ch[sz]);    return sz++;}