题意：告诉你一个母串和子串，能用多少种不同的方案组合出母串。
思路：字典树（显然）+DP
DP： dp[i]+=dp[j+1] i<=j<=m-1,且i到j的字符串能在字典树中找到。也就等价dp[i]=1*dp[j+1]
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <vector>
using namespace std; #define LL long long
const int maxn=*;
const int maxm=3e5+;
const int mod=;
struct Trie
{
int ch[maxn][];
int val[maxn];
int sz;
Trie()
{
sz=;
memset(ch[],,sizeof(ch[]));
}
int idx(char c)
{
return c-'a';
} void insert(char *s,int v)
{
int i,u=,n=strlen(s);
for(i=; i<n; i++)
{
int c=idx(s[i]);
if(!ch[u][c])
{
memset(ch[sz],,sizeof(ch[sz]));
val[sz]=;
ch[u][c]=sz++;
}
u=ch[u][c];
}
val[u]=v;
}
} e;
char str[maxm];
char a[];
LL dp[maxm];
int main()
{
int tt=;
while(scanf("%s",str)!=EOF)
{
int i,j,k,n,m,u;
scanf("%d",&n);
memset(e.ch[],,sizeof(e.ch[]));
e.sz=;
for(i=; i<n; i++)
{
scanf("%s",a);
e.insert(a,);
}
m=strlen(str);
memset(dp,,sizeof(dp));
dp[m]=;
for(i=m-; i>=; i--)
{
u=;
for(j=i; j<m; j++)
{
int c=e.idx(str[j]);
if(!e.ch[u][c])
break;
u=e.ch[u][c];
if(e.val[u])
dp[i]+=dp[j+];
}
dp[i]%=mod;
}
printf("Case %d: %lld\n",++tt,dp[]);
}
return ;
}