很好嘛，一直都是做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++;}