uvalive3942：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1943
题意：给以一个串，然后给你一些单词，问你这个串由这些单词组成的话，可以有多少种组成方式。
题解：这是白书上的一道题目。开始，觉得是DP，但是不知道怎么搞。看了白书上的解释，慢慢的才弄了出来。用dp【i】表示从i到strlen（s）-1最多的组成方式，即以字符i开头。这样的话，就很明显了，dp【i】=sum(dp[i+len(x)])(x是i.....len-1的前缀)，那么只要查询i....len-1之间的前缀，如果找到一个前缀，就更新。通过这一题，有了更深的体会，Trie树的另外一个名字，前缀树。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define maxn 1100000
using namespace std;
int dp[];
char str[];
int current;
struct Nod { //0为无效值
int lnk[], val;
char ss[];
void init() {
memset(lnk, , sizeof(lnk));
memset(ss, , sizeof(ss));
val = ;
}
};
const char BASE = 'a';
struct Trie {
Nod buf[maxn];
int len;
void init() {
buf[len=].init();
}
void insert(char * str) {
int now = ;
for(int i = ; str[i]; i ++) {
int & nxt = buf[now].lnk[str[i]-BASE];
if(!nxt)buf[nxt=++len].init();
now = nxt;
}
buf[now].val=;
}
void search(char * str) {
int now = ;
for(int i = ; str[i]; i ++) {
int & nxt = buf[now].lnk[str[i]-BASE];
now = nxt;
if(!nxt)return;//注意这里的返回,不然会tle
if(buf[now].val==){
dp[current]=(dp[current]+dp[current+i+])%;
}
}
}
} trie;
int n;
char ss[];
char s1[];
int main(){
int tt=;
while(~scanf("%s",str)){
trie.init();
scanf("%d",&n);
memset(dp,,sizeof(dp));
while(n--){
scanf("%s",ss);
trie.insert(ss);
}
int len=strlen(str);
dp[len]=;
for(int i=len-;i>=;i--){
current=i;
trie.search(str+i);
}
printf("Case %d: %d\n",tt++,dp[]);
}
}