子串算法建议

概述我有一个大集(100k)的短字符串(不超过100个字符),我需要快速找到所有那些具有一定的子字符串. 这将被用作用户开始输入的搜索框,系统会立即给出“建议”(字符串作为用户键入的文本的子串).与StackOverflow中的“Tag”框类似. 因为这将是互动的,它应该相当快.你推荐什么算法或数据结构？ BTW,我将使用Delphi 2007. 提前致谢. 我写了一个长的blurb,做了一堆复杂性计 我有一个大集(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.

这是浏览器和文本编辑器所做的一种工作,每次加载页面时都不会建立巨大的前缀表.

总结

以上是内存溢出为你收集整理的子串算法建议全部内容，希望文章能够帮你解决子串算法建议所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。