这个东西很简单的~(真的很简单)
打个比方吧
我们有两个单词,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了~
就这个鬼东西~