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

SuperJvRuo · 2018-07-23 16:20:18 · 个人记录

学习目标：熟练写出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 于是他错误的点名开始了

像这道题。

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

P4683 IOI2008 Type Printer 打印机