概述

Trie即前缀树,也称字典树。
根节点为空,从根到叶子结点的一条路径代表一个单词
使用Trie可以节约很多空间

实现

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
const int maxnode = 40010;
const int sigma_size = 26;

struct Trie
{
int sz;
int ch[maxnode][sigma_size];
int val[maxnode];

void clear()
{
sz = 1;
memset(ch[0],0,sizeof (ch[0]));
}

int idx(int c) { return c - 'a'; }

void insert(char *s,int v)
{
int u = 0,n = strlen(s);
for(int i=0;i<n;++i)
{
int c = idx(s[i]);
if(!ch[i][c]) //结点不存在,新建结点
{
memset(ch[sz],0,sizeof (ch[sz]));
val[sz] = 0; //中间结点附加信息为0
ch[u][c] = sz++;
}
u = ch[u][c]; // 向下
}
val[u] = v; //附加信息为v,
}

void find_pre(const char *s,int len,vector<int>& ans)
{
int u = 0;
for(int i=0;i<len;++i)
{
int c = idx(s[i]);
u = ch[u][c];
if(!u) break;
if(val[u]!=0) ans.push_back(val[u]);
}
}

};

int main()
{
Trie trie;
trie.clear();
int n;
scanf("%d",&n);
char s[100];
for(int i = 1;i<=n;++i) scanf("%s",s),trie.insert(s,i);
vector<int> ans;
scanf("%s",s);
trie.find_pre(s,strlen(s),ans);
printf("%d\n",ans.size());
for(int i=0;i<ans.size();++i) printf("%d ",ans[i]);
return 0;
}

题目

la3942

用Trie把集合处理出来,然后dp
$d_i$表示s[i..n]可能的组合情况
$$d_i = \sum d_{i+len(x)} \; x 为字典中元素%$$
其中s[i..i+len(x)]为s[i..n]前缀

每次通过字典树找前缀即可