题解：UVA1401 Remember the Word
这道题所用的算法是 $\texttt{Trie + DP}$。
我们设 $dp[i]$ 表示长单词 $S$ 的前 $i$ 个长度的方案数，则有(保证 $S_{j\cdots i}$ 是一个单词)：
如果使用暴力进行两层循环，不用说肯定超时。由题可知只有 $26$ 个字母，因此可以把长单词 $S$ 建成一棵字典树，然后枚举起点位置，直到找到一个单词结点，便可以进行一次转移。
优化之后，因为题目中说每个单词长度不超过 $100$，因此最多搜索到深度为 $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
| #include <iostream>
#include <cstdio>
#include <cstring>
#define mod 20071027
using namespace std;
char sen[300005];
int n,num; int ch[400005][26],tot,cnt[400005],dp[400005];
struct Trie
{
void init ()
{
tot = 0;
memset (ch,-1,sizeof (ch));
memset (cnt,0,sizeof (cnt));
memset (dp,0,sizeof (dp));
}
void insert (char *str)
{
int len = strlen (str),p = 0;
for (int i = 0;i < len;++i)
{
if (ch[p][str[i] - 'a'] == -1) ch[p][str[i] - 'a'] = ++tot;
p = ch[p][str[i] - 'a'];
}
++cnt[p];
}
void find (int x)
{
int len = strlen (sen),p = 0;
for (int i = x;i < len;++i)
{
if (ch[p][sen[i] - 'a'] == -1) return ;
p = ch[p][sen[i] - 'a'];
if (cnt[p])
{
if (x - 1 < 0) dp[i] += 1;
else dp[i] += dp[x - 1];
dp[i] %= mod;
}
}
}
};
int main ()
{
while (scanf ("%s",sen) != EOF)
{
++num;
Trie word;
word.init ();
scanf ("%d",&n);
for (int i = 1;i <= n;++i)
{
char s[105];scanf ("%s",s);
word.insert (s);
}
int len = strlen (sen);
for (int i = 0;i < len;++i) word.find (i);
printf ("Case %d: %d\n",num,dp[len - 1]);
}
return 0;
}
|
