UVALive 3942 (Remember the Word)[Trie]

·· / ·– ·· ·-·· ·-·· / ·–· · ·-· ··· ·· ··· - / ··- -· - ·· ·-·· / ·· / ·– ·· -·
这题是刘汝佳老师《算法竞赛入门经典-训练指南》上字符串一节的例题，下文的思路直接来自书上的解析，代码来自代码仓库（需翻墙）
可以想到这样的递推法：令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不会超时。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
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;
}