这个数据结构是什么?

我得到了一组(没有重复)二进制字符串与任意长度和数字,并需要找出是否有任何字符串是其他字符串的前缀。对于小集合和长度较小的字符串,它很容易,只需通过读取每个字符串来构建二叉树,每当我找到前缀匹配时,即时完成。但是有很多长字符串的字符串,这种方法效率不高。只是想知道这个数据结构和算法是什么。霍夫曼树?尝试(基数树)?还是什么?谢谢。     
已邀请:
我会带着特里去。使用trie,插入所有字符串,这样每个字符串的最后一个节点都标有一个标志,然后对于每个字符串,沿着它的路径走,检查页面上的任何节点是否设置了它的标志。如果是,则结束于该节点的字符串是您正在分析的字符串的前缀。 假设n =字符串数且k =平均长度,插入和分析两者总共取O(kn)。 前缀树(节点长于单个字符的trie)可能更有效,但不容易实现。     

要回复问题请先登录注册