algorithm - 哈希表和子串匹配

Question

我有数百个键，例如：

我有与这些键相关的数据，数据是一个字符串，最后有相关的键。

我希望使用哈希表和哈希函数根据键记录数据，并且我希望能够从表中检索数据。

我知道使用哈希函数和哈希表，这里没有问题。

但;

我应该给程序一个字符串，它作为子字符串发生并检索匹配键的数据。

例如：

我必须给“红色”并且必须能够得到

作为输出。

或者

我必须给“苹果”并且必须能够得到

作为输出。

如果它们具有匹配的子字符串，我只能考虑搜索所有键，还有其他解决方案吗？如果我搜索每个查询的所有关键字符串，则不需要使用散列，没有意义，是吗？

但是，搜索子字符串的所有键是 O(N)，我希望用 O(1) 解决问题。

通过散列，我可以将密钥（例如“redapple”）散列到例如943，并将“maninred”散列到例如332。

并且查询人给出字符串“red”我如何从943和332中找出键具有“red”子字符串？这超出了我的cs思维能力。

感谢您的任何建议，想法。

score 3 · Accepted Answer

它不能在哈希表中很好地完成。给定 aa 子字符串 - 您无法预测整个字符串^{1的散列结果}

一个合理的替代方法是使用后缀树。后缀树中的每个终端都将保存完整字符串的引用列表，该后缀与之相关。

给定一个 substring t，如果它确实是s你的集合中 some 的子串，那么有一个-的后缀x，即的前缀。通过在读取时遍历后缀树，并找到从您从那里到达的节点可到达的所有终端。这些终端包含所有需要的字符串。stxt

(1)假设合理的hash函数，如果hashCode() == 0对于每个元素，可以明显的预测出hash值。

score 3 · Accepted Answer

可能您应该对 n-gramm 使用反转索引，相同的方法用于拼写校正。对于redapple一词，您将有以下一组 3-gramms red, eda, dap, app, ppl, ple。对于每个 n-gramm，您将有一个包含它的字符串列表。例如对于红色它将是

红色 -> maninred, redapple

此列表中的单词必须排序。当您想查找包含 aa 给定子字符串的所有字符串时，您在 n-gramm 上搜索子字符串并截取 n-gramm 的单词列表。

这个算法不是 O(n)，但它练习它有足够的速度。

score -1 · Accepted Answer

我最近研究了这个问题，我确信这是做不到的。我希望哈希表能像你一样帮助我提高搜索速度，但这让我很失望。

3 回答 3