题意：给出一个单词text，仅仅由小写字母组成，并给出若干个单词word[i]，用word[i]去拼接出text，问有多少种方法
分析：典型的Trie的题目。第一次看训练指南的时候套用刘汝佳的模板结果wa（显然我不会用），后来发现很多人都是用指针写的，大部分Trie的题目用指针就能ac，索性自己写了一份使用指针的Trie的模板
代码：
View Code
1 #include <string.h> 2 #include <stdio.h> 3 #include <iostream> 4 #include <vector> 5 using namespace std; 6 #define DEBUG 7 const int brnum = 26; 8 struct Trie_node{ 9 Trie_node *br[brnum]; //branches,分支总数 10 int val; //value of node，一般单词节点为1，非单词节点为0 11 Trie_node():val(0){memset(br, 0, sizeof(br));} 12 }; 13 struct Trie{ 14 Trie_node* root; 15 Trie(){root=new Trie_node();} 16 int idx(char c){return c-'a';} 17 void insert(const char *s, int v){ 18 int n = strlen(s), i; 19 Trie_node* cur = root; 20 for(i=0; i<n; i++) { 21 int c = idx(s[i]); 22 if(!cur->br[c]){ 23 Trie_node *tmp = new Trie_node(); 24 cur->br[c] = tmp; 25 cur->br[c]->val=0; //这里改了好久~ 26 } 27 cur = cur->br[c]; 28 } 29 cur->val = v; 30 } 31 void find_prefixes(const char *s, int len, vector<int>& ans) { 32 Trie_node* cur=root; 33 for(int i=0; i<len; i++) { 34 if(s[i]=='\0') break; 35 int c=idx(s[i]); 36 if(!cur->br[c]) break; 37 cur=cur->br[c]; 38 if(cur->val) ans.push_back(cur->val); // 找到一个前缀 39 } 40 } 41 }; 42 const int maxl=300000+10; // 文本串最大长度 43 const int maxw=4000+10; // 单词最大个数 44 const int maxwl=100+10; // 每个单词最大长度 45 const int MOD=20071027; 46 int d[maxl], len[maxw], n; 47 char text[maxl], word[maxwl]; 48 int main() { 49 #ifndef DEBUG 50 freopen("in.txt", "r", stdin); 51 #endif 52 int cas=1, i, j; 53 while(scanf("%s%d", text, &n)!=EOF) { 54 Trie trie; 55 for(i=1; i<=n; i++) { 56 scanf("%s", word); 57 len[i] = strlen(word); 58 trie.insert(word, i); 59 } 60 memset(d, 0, sizeof(d)); 61 int L=strlen(text); 62 d[L]=1; 63 for(i=L-1; i>=0; i--) { 64 vector<int> p; 65 trie.find_prefixes(text+i, L-i, p); 66 for(j=0; j<p.size(); j++) 67 d[i]=(d[i]+d[i+len[p[j]]])%MOD; 68 } 69 printf("Case %d: %d\n", cas++, d[0]); 70 } 71 return 0; 72 }
不过这题的dp第一次做的时候没看懂刘汝佳的公式，第二次做才搞懂。。
