字符串前缀树：
单纯的暴力会超时，所以采用前缀树。
先用单词构造前缀树，然后用母串遍历查询，每次查询不会超过一百，所以时间复杂度不会超过3 * 10 ^ 7；至于怎么查询可以从前往后递推，也可以从后往前递推，
从前往后递推公式：
d[j] += d[i - 1]；
//#pragma comment(linker, "/STACK:1024000000,1024000000") #include#include #include #include #include #include #include #include #include #include #define INF 0x3fffffff #define inf -0x3f3f3f3f #define N 300010 #define M 4000010 #define LL long long #define mod 20071027 using namespace std; int n, sz; char s[N], str[110]; int ch[M][26], val[M], sum[N]; void init(){ memset(ch[0], 0, sizeof(ch)); sz = 1; int len = strlen(s); for(int i = 1; i <= len; ++ i) sum[i] = 0; sum[0] = 1; } int idx(char c){ return c - 'a'; } void insert(){ int u = 0, len = strlen(str); for(int i = 0; i < len; ++ i){ int c = idx(str[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 query(){ int len = strlen(s); for(int i = 1; i < len; ++i){ int u = 0; for(int j = i; j < len; ++ j){ int c = idx(s[j]); if(!ch[u][c]) break; u = ch[u][c]; if(val[u]) sum[j] = (sum[i - 1] + sum[j]) % mod; } } } int main() { // freopen("in.txt", "r", stdin); int t = 0; while(scanf("%s", s + 1) != EOF){ s[0] = '1'; init(); scanf("%d", &n); for(int i = 0; i < n; ++ i){ scanf("%s", str); insert(); } query(); int len = strlen(s); printf("Case %d: %d\n", ++ t, sum[len - 1] % mod); } return 0; }