database - 如何有效地在大型数据集中搜索子字符串？

我有一大套短线。在包含子字符串的项上筛选列表的算法和索引策略是什么？例如，假设我有一个列表：

val words = List(
  "pick",
  "prepick",
  "picks",
  "picking",
  "kingly"
  ...
)

如何找到包含子字符串“king”的字符串？我可以像这样粗暴地解决这个问题：

words.filter(_.indexOf("king") != -1) // yields List("picking", "kingly")

这只适用于小型设备；今天我需要支持1000万个字符串，未来目标是数十亿。显然我需要建立一个索引。什么样的索引？
我已经研究过使用存储在mysql中的ngram索引，但我不确定这是否是最好的方法。当搜索字符串超过ngram大小时，我不确定如何最佳地查询索引。
我也考虑过使用lucene，但这是围绕令牌匹配而优化的，而不是子串匹配，而且似乎不支持简单子串匹配的要求。lucene确实有一些与ngram相关的类（org.apache.lucene.analysis.ngram.NGramTokenFilter是一个例子），但是这些类似乎是用于拼写检查和自动完成用例，而不是子字符串匹配，而且文档很薄。
我应该考虑什么其他的算法和索引策略？是否有任何开源库支持此功能？SQL或Lucene策略（如上）是否可以正常工作？
说明需求的另一种方法是使用sql：

SELECT word FROM words WHERE word LIKE CONCAT('%', ?, '%');

其中?是用户提供的搜索字符串，结果是包含搜索字符串的单词列表。

最佳答案

最长的字有多大？
如果这大约是7-8个字符，您可以找到每个字符串的所有子字符串，并在trie中插入该子字符串（aho corasik-http://en.wikipedia.org/wiki/Aho-Corasick中使用的子字符串）。
建造这棵树需要一些时间，但随后搜索所有发生的事件将是o（长度（搜索词））。

关于database - 如何有效地在大型数据集中搜索子字符串？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11782872/