考虑到NOIP从过去的不考数据结构，到现在的考察范围越来越广，考察难度越来越高，所以，今天我们来介绍一种简单数据结构——字典树，及其基本原理和算法实现。
字典树能干啥
字典树，又名Trie树，是一种用于处理单一字符串与多个字符串相互之间匹配关系的数据结构。字典树作为AC自动机的基础，不仅在字符串处理领域有巨大的作用，同时在位运算、动态规划等方面也占有重要的地位。
关于字典树的应用详解，可以在公众号【信息学竞赛从入门到巅峰】中获取哦。
字典树长啥样
字典树上的每条边代表了一个字母（关键）。从根节点到任意一个节点有且仅有一条路径，而这个节点就代表了由这条路径上的字符依次连接组成的单词。下面举一个例子：
一棵可能的字典树
在这个例子中，字典树由左侧的6个字符串共同构成。树上的边的权值为字母，代表这个一个字符串的下一个字符是什么。点上的标号是对应的字符串的序号（左侧字符串从上到下，从1开始标号）。
字典树如何构造
通过这个例子，构造字典树的算法就已经很显然了。
1、先定义一个根节点root。
2、读入一个字符串后，从根节点开始，沿着对应字母的边往下走。
a. 如果当前节点没有当前字母的边，那么新构造一个节点，将当前节点和新建节点连一条当前字母的边，然后沿着这条边往下走。
b. 如果当前节点有当前字母的边，那么直接沿着这条边往下走。
3、处理完一个字符串后，在最终停留的节点进行标记，表示这个节点代表的字符串是出现过的一个串。
Code
/*
Tips：
本代码使用了面向对象的编程思想，竞赛中可不采用。
本代码在构造字典树时使用了指针，读者可根据实际使用数组模拟指针。
*/
struct node {
int id;
node* nxt[26];
node() {
id = -1;
for (int i = 0; i < 26; ++i)
nxt[i] = NULL;
}
};
class TrieTree {
public:
TrieTree() { root = new node; }
int get_id(node* x) { return x->id; }
node* get_root() { return root; }
node* get_nxt(node* x, char k) { return x->nxt[k - 'a']; }
void insert(char* c, int id) {
int len = strlen(c);
node* now = root;
for (int i = 0; i < len; ++i) {
int x = c[i] - 'a';
if ((now->nxt[x]) == NULL)
now->nxt[x] = new node;
now = now->nxt[x];
}
now->id = id;
}
private:
node* root;
}t;
【信息学竞赛从入门到巅峰】，一个专注于分享OI/ACM常用算法及知识的公众号。
网友评论