@[FullBT](/user/328170) trie 的最大大小要开到字符串的总长吧（（（
by zimujun @ 2021-02-27 09:05:24
trie树的空间占用不太明朗，为了不给自己找麻烦，可以开所有字母所占用的空间，如果空间要爆的话就往极限开就行。
by Terrible @ 2021-02-27 09:27:18
hers he his him
~~~~
i-m
/ \
root-h s
\
e-r-s
~~~~
加上根一共8个节点，所有字母长度为 $4+2+3+3=12$ 可以开13个节点。
by Terrible @ 2021-02-27 09:31:00
@[Terrible](/user/195942) 怎么就不太明朗了（
by expect @ 2021-02-27 09:34:52
@[zimujunqwq](/user/118196)
不好意思刚刚有点事
所以是如果我最多有8个字符串，每个字符串只有1和2，每个字符串长度为10
数组是开到$trie[8 * 10 + 1][3]$吗？
by Kalium @ 2021-02-27 10:32:39
@[expect](/user/242901) 就是说要在一个不多一个不少的情况下开一个数组存trie树，几乎只有在插入之后才知道要开多少空间，往往预算必须多一些。
by Terrible @ 2021-02-27 10:55:45
@[Terrible](/user/195942) 都开字符串长度就没事了
其实上界大概是是字符串长度$-\sum_{i=0}^{floor(log_{|S|}n)} n-|S|^i$，$|S|$是字符集大小
不过没人去搞这么麻烦的东西吧
by expect @ 2021-02-27 11:11:13
@[FullBT](/user/328170) 是
by expect @ 2021-02-27 11:13:09
@[Terrible](/user/195942) 一个不多一个不少基本上动态开点的数据结构都做不到吧，~~除非你整个vector~~
by expect @ 2021-02-27 11:13:55
@[expect](/user/242901)
谢谢
by Kalium @ 2021-02-27 11:14:36