题目连接：https://vjudge.net/problem/UVALive-3942
trie树
dp[i]=sum(dp[i+len(x)]%mod;
dp[i]表示从字符i开始的字符串的分解方案方案数，x是s[i……L]的前缀
1 #include<cstdio> 2 #include<cstring> 3 const int maxnode=500010; 4 const int sigma=26; 5 const int N=300010; 6 const int mod=20071027; 7 int ch[maxnode][sigma]; 8 int val[maxnode]; 9 int sz; 10 inline int id(char c) {return c-'a';} 11 12 void trie_init() 13 { 14 sz=1; 15 memset(ch[0],0,sizeof(ch[0])); 16 } 17 18 void inser(char *s,int v) 19 { 20 int u=0; 21 for(int i=0;s[i];i++) 22 { 23 int c=id(s[i]); 24 if(!ch[u][c]) 25 { 26 memset(ch[sz],0,sizeof(ch[sz])); 27 val[sz]=0; 28 ch[u][c]=sz++; 29 } 30 u=ch[u][c]; 31 } 32 val[u]=v; 33 } 34 int num,dp[N],st; 35 void query(char *s) 36 { 37 int u=0; 38 for(int i=0;s[i];i++) 39 { 40 int c=id(s[i]); 41 if(ch[u][c]) 42 { 43 u=ch[u][c]; 44 if(val[u]) num=(num+dp[st+i+1])%mod; // 45 } 46 else return; 47 } 48 } 49 int main() 50 { 51 char s[N],p[110]; 52 int k=0; 53 while(scanf("%s",s)!=EOF) 54 { 55 trie_init(); 56 int m; 57 scanf("%d",&m); 58 while(m--) 59 { 60 scanf("%s",p); 61 inser(p,1); 62 } 63 int len=strlen(s); 64 dp[len]=1; 65 for(int i=len-1;i>=0;i--) 66 { 67 num=0; 68 st=i; 69 query(&s[i]); 70 dp[i]=num; 71 } 72 printf("Case %d: %d ",++k,dp[0]); 73 } 74 return 0; 75 }
lrj：
1 // LA3942 Remember the Word 2 // Rujia Liu 3 #include<cstring> 4 #include<vector> 5 using namespace std; 6 7 const int maxnode = 4000 * 100 + 10; 8 const int sigma_size = 26; 9 10 // 字母表为全体小写字母的Trie 11 struct Trie { 12 int ch[maxnode][sigma_size]; 13 int val[maxnode]; 14 int sz; // 结点总数 15 void clear() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); } // 初始时只有一个根结点 16 int idx(char c) { return c - 'a'; } // 字符c的编号 17 18 // 插入字符串s，附加信息为v。注意v必须非0，因为0代表“本结点不是单词结点” 19 void insert(const char *s, int v) { 20 int u = 0, n = strlen(s); 21 for(int i = 0; i < n; i++) { 22 int c = idx(s[i]); 23 if(!ch[u][c]) { // 结点不存在 24 memset(ch[sz], 0, sizeof(ch[sz])); 25 val[sz] = 0; // 中间结点的附加信息为0 26 ch[u][c] = sz++; // 新建结点 27 } 28 u = ch[u][c]; // 往下走 29 } 30 val[u] = v; // 字符串的最后一个字符的附加信息为v 31 } 32 33 // 找字符串s的长度不超过len的前缀 34 void find_prefixes(const char *s, int len, vector<int>& ans) { 35 int u = 0; 36 for(int i = 0; i < len; i++) { 37 if(s[i] == ' ') break; 38 int c = idx(s[i]); 39 if(!ch[u][c]) break; 40 u = ch[u][c]; 41 if(val[u] != 0) ans.push_back(val[u]); // 找到一个前缀 42 } 43 } 44 }; 45 46 #include<cstdio> 47 const int maxl = 300000 + 10; // 文本串最大长度 48 const int maxw = 4000 + 10; // 单词最大个数 49 const int maxwl = 100 + 10; // 每个单词最大长度 50 const int MOD = 20071027; 51 52 int d[maxl], len[maxw], S; 53 char text[maxl], word[maxwl]; 54 Trie trie; 55 56 int main() { 57 int kase = 1; 58 while(scanf("%s%d", text, &S) == 2) { 59 trie.clear(); 60 for(int i = 1; i <= S; i++) { 61 scanf("%s", word); 62 len[i] = strlen(word); 63 trie.insert(word, i); 64 } 65 memset(d, 0, sizeof(d)); 66 int L = strlen(text); 67 d[L] = 1; 68 for(int i = L-1; i >= 0; i--) { 69 vector<int> p; 70 trie.find_prefixes(text+i, L-i, p); 71 for(int j = 0; j < p.size(); j++) 72 d[i] = (d[i] + d[i+len[p[j]]]) % MOD; 73 } 74 printf("Case %d: %d ", kase++, d[0]); 75 } 76 return 0; 77 }