我有一大组 (100k) 短字符串(不超过 100 个字符)，我需要快速找到所有具有特定子字符串的字符串。
这将用作搜索框，用户在其中开始输入，系统会立即给出“建议”(将用户输入的文本作为子字符串的字符串)。类似于 StackOverflow 中的“标签”框。
因为这将是交互式的，所以它应该非常快。您为此推荐什么算法或数据结构？
顺便说一句，我将使用 Delphi 2007。
提前致谢。
最佳答案
我写了一个很长的简介，做了一堆复杂性计算和 xzibit 笑话(树中树，所以你可以在查找时查找)，但后来意识到这比我想象的要容易。浏览器一直这样做，它们永远不会在您每次加载页面时预先计算大表。
http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
这意味着您将 10 万个字符串组合成一个长字符串。然后您获取查询子字符串，并遍历您的大字符串，寻找您的匹配项。但你不是按字符跳跃(这意味着你正在查看 100k*100 次迭代)。您正在跳转子串的长度，因此您的子串越长，跳转得越快。
这是一个很好的例子:http://userweb.cs.utexas.edu/users/moore/best-ideas/string-searching/fstrpos-example.html
他们正在搜索字符串 EXAMPLE。
这是浏览器和文本编辑器所做的事情，它们不会在您每次加载页面时真正构建巨大的前缀表。
关于algorithm - 子串算法建议，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3728394/