我有一大组（100k）的短字符串（不超过100个字符），我需要快速找到所有有特定子字符串的字符串。
这将被用作一个搜索框，用户在其中开始键入，系统立即给出“建议”（作为用户键入的文本的子字符串的字符串）。类似stackoverflow中“tag”框的东西。
因为这是交互式的，所以应该很快。对此，您建议使用什么算法或数据结构？
顺便说一下，我将使用Delphi2007。
提前谢谢。
最佳答案
我写了一个长的短文，做了大量的复杂计算和XZiBIT笑话（树上的树，这样你可以在查阅时查阅），但后来意识到这比我想象的要容易。浏览器总是这样做，而且每次加载页面时，浏览器都不会预计算大表。
http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
它的意思是你把你的100k串合并成一个长串。然后取查询子字符串，遍历大字符串，寻找匹配项。但你不是在按角色跳跃（这意味着你在看100k*100次迭代）。你在跳你的子串的长度，所以你的子串越长，这就越快。
这里有一个很好的例子：http://userweb.cs.utexas.edu/users/moore/best-ideas/string-searching/fstrpos-example.html
他们正在寻找字符串示例。
这是浏览器和文本编辑器所做的事情，它们并不是每次你加载一个页面时都会构建巨大的前缀表。