现在的位置: 首页 > 综合 > 正文

trie树

2017年04月27日 ⁄ 综合 ⁄ 共 366字 ⁄ 字号 评论关闭

这个东西很简单的~(真的很简单)

打个比方吧

我们有两个单词,orz  open

那么如果我们用trie树储存的话

z    ->r   -↓

               o

n->e->p-↑

->代表指向它的上级~

如果我们再加一个单词opp

那么就得再搞一个节点p指向e的上级p

但如果我有两个单词是he she

怎么办?。。

我们以某一个节点为根(不含任何字母~),然后把h s接到根上,

然后继续拓展就行了

某实现方法:


开数组,trie[i][j]表示第i个节点下一个字符为j的子串的位置

然后如何确立终点呢?开个ok[i] = true 表示存在第i个节点为终点的串


感觉就像一个很NB的hash

但他还有更多的妙用~

比如说给你一个串,让你统计它的不同的非空子串的个数

我们就可以枚举每一个起点,然后把后边的串搞到trie树中间去,最后统计一下ok[]中的true就OK了~

就这个鬼东西~

【上篇】
【下篇】

抱歉!评论已关闭.