题意：告诉你一个母串和子串，能用多少种不同的方案组合出母串。
思路：字典树（显然）+DP
DP： dp[i]+=dp[j+1] i<=j<=m-1,且i到j的字符串能在字典树中找到。也就等价dp[i]=1*dp[j+1]
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <cstdlib> 5 #include <iostream> 6 #include <algorithm> 7 #include <queue> 8 #include <map> 9 #include <vector> 10 using namespace std; 11 12 #define LL long long 13 const int maxn=4001*101; 14 const int maxm=3e5+10; 15 const int mod=20071027; 16 struct Trie 17 { 18 int ch[maxn][26]; 19 int val[maxn]; 20 int sz; 21 Trie() 22 { 23 sz=1; 24 memset(ch[0],0,sizeof(ch[0])); 25 } 26 int idx(char c) 27 { 28 return c-'a'; 29 } 30 31 void insert(char *s,int v) 32 { 33 int i,u=0,n=strlen(s); 34 for(i=0; i<n; i++) 35 { 36 int c=idx(s[i]); 37 if(!ch[u][c]) 38 { 39 memset(ch[sz],0,sizeof(ch[sz])); 40 val[sz]=0; 41 ch[u][c]=sz++; 42 } 43 u=ch[u][c]; 44 } 45 val[u]=v; 46 } 47 } e; 48 char str[maxm]; 49 char a[101]; 50 LL dp[maxm]; 51 int main() 52 { 53 int tt=0; 54 while(scanf("%s",str)!=EOF) 55 { 56 int i,j,k,n,m,u; 57 scanf("%d",&n); 58 memset(e.ch[0],0,sizeof(e.ch[0])); 59 e.sz=1; 60 for(i=0; i<n; i++) 61 { 62 scanf("%s",a); 63 e.insert(a,1); 64 } 65 m=strlen(str); 66 memset(dp,0,sizeof(dp)); 67 dp[m]=1; 68 for(i=m-1; i>=0; i--) 69 { 70 u=0; 71 for(j=i; j<m; j++) 72 { 73 int c=e.idx(str[j]); 74 if(!e.ch[u][c]) 75 break; 76 u=e.ch[u][c]; 77 if(e.val[u]) 78 dp[i]+=dp[j+1]; 79 } 80 dp[i]%=mod; 81 } 82 printf("Case %d: %lld ",++tt,dp[0]); 83 } 84 return 0; 85 }