·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
这题是刘汝佳老师《算法竞赛入门经典-训练指南》上字符串一节的例题，下文的思路直接来自书上的解析，代码来自代码仓库（需翻墙）
可以想到这样的递推法：令d(i)表示从字符i开始的字符串（即后缀S[i..L]）的分解方案数，则d(i)=sum{d(i+len(x))|x为一个单词并且是S[i..L]的一个前缀}。
如果直接枚举x并判断其是否为S[i..L]的前缀会超时，这时可以构建一颗Trie树，并插入所有单词，然后在Trie树中「查找」S[i..L]，经过一个单词结点，就能找到一个上述状态转移方程的x，因为每个单词长度最长为100，所以查找次数最多300000 * 100不会超时。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
const int maxnode = 4000 * 100 + 10;
const int sigma_size = 26;
const int maxl = 300000 + 10;
const int maxw = 4000 + 10;
const int maxwl = 100 + 10;
const int MOD = 20071027;
struct Trie {
int ch[maxnode][sigma_size];
int val[maxnode];
int sz;
void clear() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); }
int idx(char c) { return c - 'a'; }
void insert(const char *s, int v) {
int u = 0, n = strlen(s);
for (int i = 0; i < n; i++) {
int c = idx(s[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] = v;
}
void find_prefixes(const char *s, int len, std::vector<int> &ans){
int u = 0;
for(int i = 0; i < len; i++) {
if (s[i] == '\0') break;
int c = idx(s[i]);
if (!ch[u][c]) break;
u = ch[u][c];
if (val[u] != 0) ans.push_back(val[u]);
}
}
};
int d[maxl], len[maxw], S;
char text[maxl], word[maxwl];
Trie trie;
int main() {
int cas = 1;
while(scanf("%s%d", text, &S) == 2) {
trie.clear();
for (int i = 1; i <= S; i++) {
scanf("%s", word);
len[i] = strlen(word);
trie.insert(word, i);
}
memset(d, 0, sizeof(d));
int L = strlen(text);
d[L] = 1; //如果x恰好等于S[i..L]，则d应该加1
for(int i = L-1; i >= 0; i--) {
std::vector<int> p;
trie.find_prefixes(text+i, L-i, p);
for(int j = 0; j < p.size(); j++)
d[i] = (d[i] + d[i+len[p[j]]]) % MOD;
}
printf("Case %d: %d\n", cas++, d[0]);
}
return 0;
}