字典树(Trie树)

update 2020.06.21 感谢@pengyule 提出了问题，更改了cnt的初始值

update 2020.06.22 添加了时间复杂度

先看看百度是怎么定义的

字典树，又称单词查找树，Trie树
是一种树形结构，是一种哈希树的变种
典型应用是用于统计，排序和保存大量的字符串(但不仅限于字符串)
所以经常被搜索引擎系统用于文本词频统计
它的优点是：利用字符串的公共前缀来减少查询时间
最大限度地减少无谓的字符串比较，查询效率比哈希树高

Trie树真是处理字符串的利器呢qwq

插入

假如我们要在树中插入cat，car，bread，break，broke，no，not，noi,就是这样的qwq:

不难想出插入的过程:

1.要插入字符串的时候,先查看深度为当前节点深度+1的节点中有没有该字符串的第深度位字符
如果有,就直接将当前节点设为这个字符所在的节点
没有就新建一个节点,并且将当前节点设为这个字符所在的节点

2.标记当前根节点(相当于标记字符串的最后一个字符,即标记整个字符串)

假如要在上图那棵树中插入字符串"nope"，过程如下：

P.S. 画得图里面的字母忘记换成小写了，请见谅

所以我们就可以写出以下代码啦qwq:

前置定义部分：

int cnt=1;//计数,把字典树的节点按照插入顺序编号
int trie[300010][26];//树
bool vis[300010];//标记

插入字符代码部分：

inline void insert(char s[]){
    int root=1,len=strlen(s);//root是根,len是字符串的长度
    for(int i=0;i<len;++i){
        int x=s[i]-'a';//'a'有时改成'A'或'0'
        if(!trie[root][x]) trie[root][x]=++cnt;//如果没有这个节点
        root=trie[root][x];
    }
    vis[root]=1;
    return;
}

不难发现，trie的插入复杂度是o(n*len)(len是字符串长度)

Q：为什么要标记呢？
A：往下看

有插入，必有查询纯属瞎扯

那么怎么查询这棵树里有没有某个字符串呢？
与插入操作类似：

1.查看有没有当前位置的字符
如果没有就没找到，就返回
否则就是有，将根设为当前字符，继续找

2.此时已经遍历完所有的字符了，发现都存在于这棵树中
但是怎么判断这个单词是否存在呢
别忘了刚刚打了标记
如果标记为1，则存在
否则不存在

代码：

inline bool find(char s[]){
    int root=1,len=strlen(s);
    for(int i=0;i<len;++i){
        int x=s[i]-'a';
        if(!trie[root][x]) return false;//如果没找到，就返回false
        root=trie[root][x];//往下查找
    }
    if(vis[root]) return true;//如果有标记，返回true
    return false;//否则返回false
}

每次查找的时间复杂度是o(len)(len为字符串长度)

真是神奇呢qwq

接下来是一道例题，来自洛谷：

于是他错误的点名开始了

字典树模板题啦，需要注意的是，这里还有一个判断是否重复，需要再加一个bool数组qwq

代码：

#include "bits/stdc++.h"
using namespace std;
int trie[500010][26],cnt=1,vis[500010],v[500010];
inline void insert(char s[]){
    int root=1,len=strlen(s);
    for(int i=0;i<len;++i){
        int x=s[i]-'a';
        if(!trie[root][x]) trie[root][x]=++cnt;
        root=trie[root][x];
    }
    vis[root]=1;
    return;
}
inline void find(char s[]){
    int root=1,len=strlen(s);
    for(int i=0;i<len;++i){
        int x=s[i]-'a';
        if(!trie[root][x]){puts("WRONG");return;}
        root=trie[root][x];
    }
    if(vis[root]&&v[root]) puts("REPEAT");
    if(vis[root]&&!v[root]){puts("OK");v[root]=1;}
}
int main(){
    int n,m;
    cin>>n;
    char s[100];
    while(n--){
        scanf("%s",s);
        insert(s);
    }
    cin>>m;
    while(m--){
        scanf("%s",s);
        find(s);
    }
    return 0;
}

完结了

如果有不明白的欢迎提出建议，我会改的qwq