以树形结构存储大量字符串——字典树

学习目标：熟练写出trie树 ### 一、什么是字典树 字典树即trie树，是~~一种在工程中没有任何卵用的数据结构，~~在信息竞赛中应用广泛的数据结构。同时，它也是AC自动机的基础。 ### 二、字典树的结构 如果字符串的字符集是小写英文字母，那么字典树是26叉树。字符集有多大，每个节点就有多少个子节点。 因此，以小写英文字母为字符集，字典树的节点形式如下： ``` struct Node { int ch[26],cnt,isEnd; } ``` 其中，```ch[26]```代表26个子节点的模拟指针，```cnt```表示经过这里的字符串个数，```isEnd```表示它是几个字符串的结尾节点。这些可以根据需要增减。 不难发现，根节点到一个```isEnd!=0```的节点的路径代表一个字符串，根节点到一个```cnt!=0```的节点的路径代表一个前缀。  像这样。 ### 三、字典树的插入 首先要有一个根节点。 ``` int root=0; ``` 还要给子节点分配内存。 ``` int cnt=0; ``` 每当要加入节点时，分配下标```++cnt```。 然后，依据字符串从前到后的每个字符在字典树上走路，直到走完，一路上维护信息： ``` using std::string; void insert(string s) { int now=root; for(int i=0;i<s.length();++i) { ++node[now].cnt; if(!node[now].ch[s[i]-'a']) { node[now].ch[s[i]-'a']=++cnt; } now=node[now].ch[s[i]-'a']; } ++node[now].cnt; ++node[now].isEnd; } ``` ### 四、字典树的查询 #### 1、查询字符串 [P2580 于是他错误的点名开始了](https://www.luogu.org/problemnew/show/P2580) 像这道题。 trie树的查询和插入非常相似，只要在树上走路即可： ``` bool count(string s) { int now=root; for(int i=0;i<s.length();++i) { if(!node[now].ch[s[i]-'a']) return false; } return node[now].isEnd; } ``` #### 2、查询前缀 把最后一行改成 ``` return true; ``` 即可。 ### 五、例题 [P2922 USACO08DEC 秘密消息Secret Message](https://www.luogu.org/problemnew/show/P2922) [P4683 IOI2008 Type Printer 打印机](https://www.luogu.org/problemnew/show/P4683)