题意：给出n（n<=4000）个单词和一个字符串（len<=300000），求把这个字符串分解成若干个单词的拼接，有多少种方法
思路：Trie，先把单词建成Trie，然后进行dp，dp[i]表示以字符串中第i个字母为开头的情况，然后每个状态只要在Trie树上找到相应的字母开头的单词，，然后dp[i] = sum{dp[i + len（x）]}进行状态转移即可 这个x是n个单词中的一个，可以用Trie查询
code：
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn = 300005;const int MOD = 20071027;int ch[maxn][26];int val[maxn];int sz;int idx(char c){return c-'a';}void insert(char* s){int u = 0;int len = strlen(s);for(int i = 0; i < len; 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] = 1;}void init(){sz = 1;memset(ch[0],0,sizeof(ch[0]));int m;scanf("%d",&m);char str[105];while(m–){scanf("%s",str);insert(str);}}int d[maxn];void find(int id, char* s){d[id] = 0;int u = 0;// int len = strlen(s);for(int i = id; s[i]; i++){int c = idx(s[i]);if(!ch[u][c]) return;u = ch[u][c];if(val[u]) d[id] = (d[id]+d[i+1])%MOD;}}void solve(char* s){int len = strlen(s);d[len] = 1;for(int i = len-1; i >= 0; i–){find(i, s);}printf("%d\n",d[0]);}int main(){int cas = 0;char s[maxn];while(scanf("%s",s) != EOF){init();printf("Case %d: ",++cas);solve(s);}return 0;}注意：
find 函数中千万不能strlen（）；不然超时T_T。。因为每次调用都会求一次长度，时间复杂度是0（N*N）；
有勇气并不表示恐惧不存在，而是敢面对恐惧、克服恐惧
