子串算法建议

发布时间：2020-12-15 10:09:43 所属栏目：大数据来源：网络整理

导读：我有一个大集(100k)的短字符串(不超过100个字符),我需要快速找到所有那些具有一定的子字符串. 这将被用作用户开始输入的搜索框,系统会立即给出“建议”(字符串作为用户键入的文本的子串).与StackOverflow中的“Tag”框类似. 因为这将是互动的,它应该相当快.

我有一个大集(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.

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!