Zth's Blog

记录学习路上的点滴

0%

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
#include <iostream>
#include <cstdio>
#include <cstring>

int trie[100005][31], tot = 1; // 初始化, 且假设字符串均只由小写字母构成
bool end[100005]; // 是否是一个字符串的结尾

void Insert(char* s) // 插入一个字符串
{
int len = strlen(s), p = 1; // p为节点编号, 注意一定要从1开始, 0代表没有这个节点

for(int i = 0; i < len; i ++)
{
int ch = s[i] - 'a';

if(trie[p][ch] == 0) trie[p][ch] = ++ tot;

p = trie[p][ch];
}

end[p] = true;
}

bool Search(char* s) // 查找一个字符串是否出现过
{
int len = strlen(s), p = 1;

for(int i = 0; i < len; i ++)
{
int ch = s[i] - 'a';

p = trie[p][ch];

if(!p) return false;
}

return end[p];
}

int main()
{

}