思路：
大白里Trie的例题，开篇就是一句很容易推出....orz
这里需要Trie+DP解决。
仔细想想我们可以得到dp[i]=sum(dp[i+len[x]])。
这里需要解释一下：dp是从最后一个字母往前dp，dp[i]代表从i这个字符开始到最后一个字符的这个字符串（就是s[i,i+1,...,L]）所能拆分的个数，所以我们每次查询s[i,i+1,...,k]是否存在这个前缀，都的话就加上dp[k+1]，最后答案是dp[0]。注意dp[L+1]应该初始化为1，因为整个s[i,i+1,...,L]都是前缀就要+1种拆分方法。
这里Trie用的大白模板，自己写的一直超时也不知道为什么，把大白模板的结构体去掉也超时emmm，求大神讲解
5.15更新：今天一直尝试终于知道为什么超时了，因为之前每次query（）都会计算一次s的长度，如果s很长，询问也很多，那么在strlen（）上就会费很多时间（居然是这个原因orz），现在附上我自己的指针版
第二次代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<string>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<iostream>
#include<algorithm>
#include<sstream>
#define ll long long
const int N=300005;
const int MOD=20071027;
using namespace std;
char s[N];
int dp[N];
struct Trie{
Trie *next[26];
int num;
Trie(){
num=0;
for(int i=0;i<26;i++){
next[i]=NULL;
}
}
};
Trie *root;
void insert(char a[]){
int len=strlen(a);
Trie *p=root;
for(int i=0;i<len;i++){
int v=a[i]-'a';
if(p->next[v]==NULL) p->next[v]=new Trie();
p=p->next[v];
}
p->num=1;
}
int query(char a[],int head,int len){
Trie *p=root;
int res=0;
for(int i=head;i<len;i++){
int v=a[i]-'a';
if(!p->next[v]) return res;
p=p->next[v];
if(p->num){
res+=dp[i+1];
res%=MOD;
}
}
return res;
}
void del(Trie *p){
if(p==NULL) return;
for(int i=0;i<26;i++){
if(p->next[i]) del(p->next[i]);
}
delete p;
}
int main(){
char a[105];
int num;
int k=1;
while(~scanf("%s",s)){
root=new Trie();
scanf("%d",&num);
for(int i=0;i<num;i++){
scanf("%s",a);
insert(a);
}
int len=strlen(s);
dp[len]=1;
for(int i=len-1;i>=0;i--){
dp[i]=query(s,i,len); //这里一定要直接传入len，不然重新算会超时
}
printf("Case %d: %d
",k++,dp[0]);
del(root);
}
return 0;
}
第一次代码（数组版）：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<string>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<iostream>
#include<algorithm>
#include<sstream>
#define ll long long
const int N=300005;
const int MOD=20071027;
using namespace std;
char s[N];
int dp[N];
struct Trie
{
int ch[4*N][26];
int val[4*N];
int sz;
void reset(){memset(ch[0],0,sizeof ch[0]);memset(val,0,sizeof val);sz=1;}
int idx(char c){return c-'a';}
void insert(char *s)
{
int u=0,l=strlen(s);
for(int i=0;i<l;++i){
int c=idx(s[i]);
if(!ch[u][c]){
memset(ch[sz],0,sizeof ch[sz]);
ch[u][c]=sz++;
}
u=ch[u][c];
}
val[u]=1;
}
int query(char *s,int p)
{
int u=0,l=strlen(s),res=0;
for(int i=p;i<l;++i){
int c=idx(s[i]);
if(!ch[u][c]) return res;
u=ch[u][c];
if(val[u]){
res+=dp[i+1];
res%=MOD;
}
}
return res;
}
}T;
int main(){
char a[105];
int num;
int k=1;
while(~scanf("%s",s)){
T.reset();
memset(dp,0,sizeof(dp));
scanf("%d",&num);
for(int i=0;i<num;i++){
scanf("%s",a);
T.insert(a);
}
int len=strlen(s);
dp[len]=1;
for(int i=len-1;i>=0;i--){
dp[i]=T.query(s,i);
}
printf("Case %d: %d
",k++,dp[0]);
}
return 0;
}