LA 3942 背单词

题意：

给出一个由S个不同单词组成的字典和一个长字符串。把这个字符串分解成若干个单词的连接，有多少种方法？比如，有4个单词a、b、cd、ab，则abcd有两种分解方法：a+b+cd和ab+cd。

思路：

建立字典树，查询的时候令d(i)表示从字符i开始的字符串的分解方案数，则d(i)=sum{d(i+len(x))|单词x是S[i..L]的前缀}。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<string>
 4 #include<cstring>
 5 using namespace std;
 6 
 7 const int maxnode = 4000 * 100 + 10;
 8 const int sigma_size = 26;
 9 const int maxn = 300000 + 10;
10 char str[maxn],s[100+5];
11 int n, dp[maxn];
12 
13 
14 struct Trie
15 {
16     int ch[maxnode][sigma_size];
17     int val[maxnode];
18     int sz;
19 
20     void init()
21     {
22         sz = 1;
23         memset(ch[0], 0, sizeof(ch[0]));
24     }
25 
26     void insert(char *s, int v)
27     {
28         int u = 0, len = strlen(s);
29         for (int i = 0; i < len; i++)
30         {
31             int c = s[i] - 'a';
32             if (!ch[u][c])
33             {
34                 memset(ch[sz], 0, sizeof(ch[sz]));
35                 val[sz] = 0;
36                 ch[u][c] = sz++;
37             }
38             u = ch[u][c];
39         }
40         val[u] = v;
41     }
42 
43     int find(char *s, int pos)
44     {
45         int len = strlen(s), u = 0, ans = 0;
46         for (int i = pos; i < len; i++)
47         {
48             int c = s[i] - 'a';
49             if (ch[u][c] == 0)  break;
50             u = ch[u][c];
51             if (val[u] == 1)
52                 ans = (ans + dp[i + 1]) % 20071027;
53         }
54         return ans;
55     }
56 }T;
57 
58 
59 int main()
60 {
61     //freopen("D:\txt.txt", "r", stdin);
62     int kase = 0;
63     while (~scanf("%s", str))
64     {
65         scanf("%d", &n);
66         T.init();
67         for (int i = 0; i < n; i++)
68         {
69             scanf("%s", s);
70             T.insert(s, 1);
71         }
72         int len = strlen(str);
73         dp[len] = 1;
74         for (int i = len - 1; i >= 0; i--)
75             dp[i] = T.find(str, i);
76         printf("Case %d: %d
", ++kase, dp[0]);
77     }
78     return 0;
79 }