substring - 如何为一个字符串的所有子串构造一个后缀Trie？

Question

我想为字符串的所有子字符串构建一个节省空间的后缀树；假设字符串的长度为 5000，则子字符串的数量约为 25*10^6，并且对于每个节点，我都存储一个大小为 26 的链接数组，因此总内存 = 26*5000*5000，这是不可能的，因此运行时错误是期待。我有一个节省空间的后缀特里树的解决方案，我们在其中压缩我们没有选择的路径，因此空间的顺序大致变为线性。但我无法理解，所以任何人都可以帮助我解决这个问题。

Answer 1

不确定你的算术......但如果你只有一个字符串，你的树必须是 26n 大小。

从技术上讲，您可以用 Suffix Array + LCP Array 替换 Suffix Trie/Tree，从而保持与基本图形操作相同的速度。内存消耗将是 1 + 4 + 4 = 9n。缺点是更改原始字符串并不容易。

Answer 2

你不搜索特里树，而是搜索我认为的后缀树。压缩路径是一种方法，但我只会搜索 Ukkonen 算法。时间和空间复杂度为 n。如果您想要更好理解的内容，只需搜索 Suffix Arrays。空间复杂度也是 n，具有较低的常数（大约 6 而不是 32 左右，我不记得确切的数字）并且通过硬件更好地预测缓存。