哈希表和子串匹配

我有数百个键，例如：

• 红苹果
• maninred
• foraman
• 蓝苹果

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

• 红苹果：树上有红苹果
• maninred: 她看到了maninred
• 孔洞：他们买了现在的孔洞
• 蓝苹果：令人惊讶，但它是蓝苹果

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

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

But;

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

例如：

我必须给予"red"并且必须能够得到

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

作为输出。

or

我必须给予"apple"并且必须能够得到

• 红苹果：树上有红苹果
• 蓝苹果：令人惊讶，但它是蓝苹果

作为输出。

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

But，搜索所有键中的子字符串是 O(N)，我预计用 O(1) 解决问题。

通过散列，我可以散列一个密钥，例如“红苹果”例如943和“maninred”，例如332.

并查询 man 给出字符串“red”，我如何从中找到943 and 332键有“红色”子字符串吗？这超出了我的cs思维能力。

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

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

红色 -> maninred、红苹果

此列表中的单词必须按顺序排列。当您想要找到包含给定子字符串的所有字符串时，您可以将子字符串潜水到 n-gram 上并截取 n-gramm 的单词列表。

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