algorithm - 实现部分密钥散列的最佳方法

Question

我出现在一次采访中，我被要求编写一个用于部分密钥散列的算法，即；如果将 ABCBC 插入哈希中，则搜索任何子字符串都应返回存储的值。我的答案是创建给定键的所有可能子字符串的集合，并维护每个子字符串与其一个或多个父字符串之间的映射。然后维护所有子字符串的集合的 BST。每个节点将指向该子字符串可能匹配的实际值的集合。例如。A, AB, ABC, ABCB, ABCBC, B, BC, BCB, BCBC, C, CB, CBC 是这个字符串的可能子串。可能还有其他字符串也像 BAB 一样，其中 AB 和 B 是子字符串。所以给定 AB，它将映射到两个字符串 BAB 和 ABCBC。

还有其他更有效的方法吗？谢谢

Answer 1

将每个子字符串存储在散列中，并注明它是否是最终的，以及可能的下一个字符和前一个字符。存储所有可以在中间有这个子字符串的单词的前一个字符，以及所有有这个子字符串作为开始的单词的下一个字符。

因此，for 条目a不需要包含所有单词a。但是，如果您愿意，构建该列表很容易。同样在插入过程中，一旦您减小子字符串的大小并且发现您已经拥有当前继续的当前子字符串，您可以停止。

假设您有许多具有相同字母的单词，这将节省一些空间和插入，但代价是实际生成列表的速度变慢。最坏的情况仍然O(n*n)是一个n字母字符串。

要删除，您可以遵循类似的过程，在包含其他子字符串的任何子字符串处停止删除。