注意到单词的长度最长100，其实最糟糕复杂度应该能到O(300005*100)，需要注意的是在字典树上匹配单词时，一旦不匹配，则后面的就不会匹配，需要break出来(这个害我TLE查了半天，日！)，还有，要注意strlen的时候，那个api的复杂度貌似是O(n)的，题目中提到输入数据的不同的test case之间有一个blank line，我理解成输出不同case之间要回车，OJ居然没判成PE，而是判成WA，这两天题写的真蛋疼（吐槽下）。
#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
#include <iostream>
using namespace std; const int MAXN = ;
const int M = ; typedef long long int64; char ch[MAXN];
int64 dp[MAXN]; int id[ * ][], cnt;
bool flag[ * ]; class DicNode {
public:
bool flag;
DicNode *sons[];
DicNode() {
flag = false;
memset(sons, NULL, sizeof(sons));
}
}; class DicTree2 {
public:
DicTree2() {
cnt = ;
memset(id, -, sizeof(id));
memset(flag, false, sizeof(flag));
}
~DicTree2() { }
void insert(const char *s) {
int len = strlen(s);
int node = ;
for (int i = ; i < len; i++) {
if (id[node][s[i] - 'a'] == -) {
id[node][s[i] - 'a'] = cnt++;
}
node = id[node][s[i] - 'a'];
if (i == len - ) {
flag[node] = true;
}
}
}
bool query(const char *s) {
int len = strlen(s);
int node = ;
for (int i = ; i < len; i++) {
if (id[node][s[i] - 'a'] == -) {
return false;
}
node = id[node][s[i] - 'a'];
}
return flag[node];
}
int64 f(int b, int len) {
if (dp[b] != -) return dp[b];
dp[b] = ;
if (b == len) return dp[b] = ;
int node = ;
for (int i = b; i < len; i++) {
if (id[node][ch[i] - 'a'] != -) {
node = id[node][ch[i] - 'a'];
if (flag[node]) dp[b] = (dp[b] + f(i + , len)) % M;
} else {
break;
}
}
return dp[b];
}
}; class DicTree {
public:
DicNode *root;
DicTree() {
root = new DicNode();
}
~DicTree() {
if (NULL != root) {
free(root);
}
}
void free(DicNode *node) {
for (int i = ; i < ; i++) {
if (node->sons[i] != NULL) {
free(node->sons[i]);
}
}
delete node;
}
void insert(const char *s) {
int len = strlen(s);
DicNode *node = root;
for (int i = ; i < len; i++) {
if (node->sons[s[i] - 'a'] == NULL) {
node->sons[s[i] - 'a'] = new DicNode();
}
node = node->sons[s[i] - 'a'];
if (i == len - ) {
node->flag = true;
}
}
}
bool query(const char *s) {
int len = strlen(s);
DicNode *node = root;
for (int i = ; i < len; i++) {
if (node->sons[s[i] - 'a'] == NULL) {
return false;
}
node = node->sons[s[i] - 'a'];
}
return node->flag;
}
int64 f(int b, int len) {
if (dp[b] != -) return dp[b];
dp[b] = ;
if (b == len) return dp[b] = ;
DicNode *node = root;
for (int i = b; i < len; i++) {
if (node->sons[ch[i] - 'a'] != NULL) {
node = node->sons[ch[i] - 'a'];
if (node->flag) dp[b] = (dp[b] + f(i + , len)) % M;
} else {
break;
}
}
return dp[b];
}
}; int main() {
int c = ;
while (scanf("%s", ch) != EOF) {
int s;
scanf("%d", &s);
DicTree dic;
for (int i = ; i < s; i++) {
char str[];
scanf("%s", str);
dic.insert(str);
}
memset(dp, -, sizeof(dp));
printf("Case %d: %lld\n", ++c, dic.f(, strlen(ch)));
}
}