社区讨论

关于字典树

2024/04/14 14:48学术版参与者 4已保存回复 7

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复: 7 条
当前快照: 1 份
快照标识符: @luz616cl
此快照首次捕获于: 2024/04/14 14:49
此快照最后确认于: 2024/04/14 16:25

字典树的空间复杂度真的很高，小 Z 写的字典树空间复杂度是

O(\vert \Sigma \vert \times \sum \vert S \vert)

（小 Sigma 为字符集）。

有没有哪些可以优化的方面，或者说，对于以下几个条件，我们可以对字典树做出哪些优化？

$n$ 个长度为 $m$ 的字符串，字符集 $\Sigma$ ，字符集较小
$n$ 个长度为 $m$ 的字符串，字符集 $\Sigma$ ，字符集较大
$n$ 个长度总和为 $m$ 的字符串，字符集 $\Sigma$ ，字符集较小
$n$ 个长度总和为 $m$ 的字符串，字符集 $\Sigma$ ，字符集较大

回复

共 7 条回复，欢迎继续交流。

正在加载回复...