Trie(字典树)

Trie

字典树,就是一棵边权是字符的树,对于树上任何条从1到根的路径经过的边权序列,都能得到一个字符串。

比如有she,her,hers,his,him这几个单词,我们就可以建立这么一个Trie。

字典树可以合并相同字符的节点,所以查找时的效率特别高。

首先会发现Trie的一个特性:必有一个根节点(把根节点记为0)。然后每条边都有一个权值,权值即为字符(一般用取id的方法来当成权值)。然后那些红色的是什么东西?不难想到这几个节点就是单词节点,也就是存在字符串的节点。

那么记录son[i][j]表示i节点j编号的儿子(没有就给0,尽管0节点是根节点,但是并没有什么关系,因为不可能有边指向根节点),以及num[i]表示i节点的权值,就可以构造一棵Trie了。

Trie构造的时间复杂度为\sum LL表示字符串的长度,询问时间为Trie的最大深度(然而实际处理中这两个操作的时间复杂度可能会有所降低)。Trie不仅有高效的时间复杂度,还为AC自动机等算法提供了基础。

以上引用K神的原话

Trie树是大多数自动机的基础,所以是挺重要的。

//LOJ10049
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN=10005,MAXL=15,MAXI=15;
char s[MAXN][MAXL];
struct Trie{
    int cnt,Son[MAXN*MAXL][MAXI],W[MAXN*MAXL];
    void clear(){memset(Son,0,sizeof(Son));memset(W,0,sizeof(W));cnt=0;}
    int get(char ch){return ch-'0';}//得到节点的值
    void Insert(char *s){
        int Now=0;//当前节点
        for(int i=0,Len=strlen(s),x;i<Len;i++){
            if(!Son[Now][x=get(s[i])]) Son[Now][x]=++cnt;//新建节点
            Now=Son[Now][x];//继续插入
        }
        W[Now]++;//到叶节点时,打个标记
    }
    int Query(char *s){//查找s的前缀个数,包括了自己
        int Now=0,Sum=0;
        for(int i=0,Len=strlen(s),x;i<Len;i++)
        if(Son[Now][x=get(s[i])]) Now=Son[Now][x],Sum+=W[Now];else break;
        return Sum;
    }
}Tre;
int main(){
    int n,T;
    for(scanf("%d",&T);T;T--){
        scanf("%d",&n);Tre.clear();
        memset(s,0,sizeof(s));
        for(int i=1;i<=n;i++) scanf("%s",s[i]),Tre.Insert(s[i]);
        char t=1;
        for(int i=1;i<=n;i++) if(Tre.Query(s[i])>1){t=0;break;}
        if(t) printf("YES\n");else printf("NO\n");
    }
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部