首页 > 代码库 > 小结:trie

小结:trie

复杂度:查找O(n),维护O(n),空间O(sum(len[i]))

概要:就是每个节点对应一个字母,然后儿子有26个,查找和维护时进入对应儿子即可。

应用:在字符串匹配中多模匹配做基础结构;可以对多个字符串维护信息。

技巧及注意:

只要注意儿子节点该开多大即可。比如中秋节模拟赛之冷月葬花魂(被虐瞎)中的t1,有大小写,那么开大点儿子即可

模板请看AC自动机部分

小结:trie