概述
Trie（字典树）是一种用于实现字符串快速检索的多叉树结构。Trie的每个节点都拥有若干个字符指针，若在插入或检索字符串时候扫描到一个字符C，就沿着当前节点的C字符指针，走向该指针指向的节点。
模板
const int SIZE = 1000000;
int trie[SIZE][26], cnt = 1; // trie[i][ch]表示节点为i的节点的ch字符的指针位置，若无则为0
bool str_end[SIZE]; //记录字符串的结尾位置
void insert(char *str) {
int len = strlen(str), p = 1; //p 为指针
for (int k = 0; k < len; ++k) {
int ch = str[k] - 'a';
if (trie[p][ch] == 0) trie[p][ch] = ++cnt;
p = trie[p][ch];
}
str_end[p] = true;
}
bool search(char *str) {
int len = strlen(str), p = 1; //p 为指针
for (int k = 0; k < len; ++k) {
p = trie[p][str[k] - 'a'];
if (p == 0) return false;
}
return str_end[p];
}
例题
| 标题： | 信息学竞赛模板（七）— 字典树(Trie) |
|---|---|
| 链接： | https://www.fightingok.cn/detail/65 |
| 更新： | 2022-09-18 22:35:52 |
| 版权： | 本文采用 CC BY-NC-SA 3.0 CN 协议进行许可 |