字典树

简介

字典树,英文名Trie。顾名思义,就是一个像字典一样的树。先放一张图:

trie1

可以发现,这棵字典树用边来代表字母,而从根结点到树上某一结点的路径就代表了一个字符串。举个例子, 表示的就是字符串 caa

结构

int trie[10e6][27];//trie[i][j] 表示结点 i 的 j 字符指向的下一个结点

操作

struct trie{int nex[100000][26],cnt;
    bool exist[100000];// 该结点结尾的字符串是否存在

    void insert(char *s,int l){// 插入字符串
        int p=0;
        for(int i=0;i<l;i++){
            int c=s[i]-'a';
            if(!nex[p][c])nex[p][c]=++cnt;// 如果没有,就添加结点
            p=nex[p][c];
        }
        exist[p]=1;
    }
    bool find(char *s,int l){// 查找字符串
        int p=0;
        for(int i=0;i<l;i++){int c=s[i]-'a';
            if(!nex[p][c])return 0;
            p=nex[p][c];
        }
        return exist[p];
    }    
};

  转载请注明: Sshwy's Blog 字典树

 上一篇
字典树 |TRIE 字典树 |TRIE
字典树 |TRIE简介字典树,其实就是一颗树。但是这颗树就像字典一样,能迅速匹配字典中的字符串。 基本性质: 根结点不包含字符,除根结点外每一个结点都只包含一个字符。 从根结点到某一结点,路径上经过的字符连接起来,为该结点对应的字符串。
2018.10.01
下一篇 
概率与期望 ·expectation 概率与期望 ·expectation
概率的定义概率, 又称“或然率”、“几率”, 它是对一个随机事件的可能性的大小所作的数量方面的估计。 一个事件 A 出现的概率, 是 A 可能出现的情况与全部可能情况的比率。其计算公式为: P(A)=m(A 可能出现的情况)/n(所有可能的
2018.10.01
  目录