algorithm - 哈希表和子串匹配

Question

我有数百个键，例如:

• 红苹果
• 马宁红
• 论坛
• 蓝苹果

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

• 红苹果:树上有红苹果
• maninred:她看到了 maninred
• foraman:他们买了现在的 foraman
• blueapple:它是令人惊讶的，但它是一个 blueapple

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

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

但是；

我需要为程序提供一个字符串作为子字符串，并检索匹配键的数据。

例如:

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

• 红苹果:树上有红苹果
• maninred:她看到了 maninred

作为输出。

或

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

• 红苹果:树上有红苹果
• blueapple:它是令人惊讶的，但它是一个 blueapple

作为输出。

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

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

通过散列，我可以散列一个 key ，例如“红苹果”例如943，以及“maninred”，例如332。

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

感谢任何建议，想法。

Answer 1

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

红色 -> maninred, redapple

此列表中的单词必须排序。当您想要查找包含给定子字符串的所有字符串时，您将子字符串潜入 n-gramm 并截取 n-gramm 的单词列表。

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