我参加了一次采访，要求我编写一个部分 key 散列算法，即；如果 ABCBC 被插入到散列中，那么搜索任何子字符串应该返回存储的值。 我的答案是创建一个给定键的所有可能子字符串的集合，并维护每个子字符串与其一个或多个父字符串之间的映射。然后维护一个所有子串集合的BST。每个节点将指向该子字符串可能匹配的实际值的集合。 例如。 A、AB、ABC、ABCB、ABCBC、B、BC、BCB、BCBC、C、CB、CBC 是该字符串的可能子字符串。可能还有其他字符串，如 BAB，其中 AB 和 B 是其子字符串。 所以给定 AB，它将映射到两个字符串 BAB 和 ABCBC。
还有其他更有效的方法吗？ 谢谢
最佳答案
将每个子字符串存储在散列中，并附上是否为最终字符串的注释，以及可能的下一个字符和前一个字符。为中间可能有此子字符串的所有单词存储前一个字符，并为以该子字符串为开头的所有单词存储下一个字符。
因此 a 的条目不需要包含所有带有 a 的单词。但如果您愿意，构建该列表很容易。同样在插入过程中，只要您减小子字符串的大小并且您发现您已经拥有当前子字符串和当前延续，您就可以停止。
假设您有许多具有相同字母的单词，这将节省一些空间和插入，但代价是实际生成列表的速度会变慢。不过，对于 n 字母字符串，最坏的情况仍然是 O(n*n)。
要删除，您可以遵循类似的过程，在包含其他子字符串的任何子字符串处停止删除。
关于algorithm - 实现部分 key 散列的最佳方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10768319/