prefix-tree - 这个数据结构是什么？

Question

我得到了一组（没有重复）具有任意长度和数字的二进制字符串，并且需要找出是否有任何字符串是其他字符串的前缀。对于小集合和长度小的字符串，这很容易，只需通过读取每个字符串来构建二叉树，每当我找到前缀匹配时，我就完成了。但是对于很多长度很长的字符串，这种方法效率不高. 只是想知道什么是正确的数据结构和算法。霍夫曼树？尝试（基数树）？还是什么？谢谢。

Answer 1

我会试一试。使用 trie 插入所有字符串，使得每个字符串的最后一个节点都标有一个标志，然后对于每个字符串，沿着它的路径走并检查页面上是否有任何节点设置了它的标志。如果是，则以该节点结尾的字符串是您正在分析的字符串的前缀。

假设 n = 字符串数和 k = 平均长度，插入和分析两者总共需要 O(kn)。

前缀树（节点长于单个字符的树）可能更有效，但并不容易实现。