我有一个大集(100k)的短字符串(不超过100个字符),我需要快速找到所有那些具有一定的子字符串.
这将被用作用户开始输入的搜索框,系统会立即给出“建议”(字符串作为用户键入的文本的子串).与StackOverflow中的“Tag”框类似.
因为这将是互动的,它应该相当快.你推荐什么算法或数据结构？
BTW,我将使用Delphi 2007.
提前致谢.
解决方法
我写了一个长的blurb,做了一堆复杂性计算和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
他们正在搜索字符串EXAMPLE.
这是浏览器和文本编辑器所做的一种工作,每次加载页面时都不会建立巨大的前缀表.