使用什么算法来匹配字符串的开头

例子：

folks 
fort 
garage 
grabbed 
grandmother 
habit 
happily 
harry 
heading 
hunter

我喜欢搜索字符串“HA”和算法返回哪里哪里字符串与“哈”开头的列表的开始，在此情况下，“习惯” 。

当然，我不会一个一个地去，因为名单是巨大的。我可以做一些预处理来对列表进行排序，或者将其放入一个使这种搜索快速进行的结构。

有什么建议吗？

我假设有多个搜索前缀，如果你只需要搜索列表，一旦它没有意义的排序它。 –

列表有多大？它是TB级数据还是数百万条目？ – user1952500

那么你想要一个类型的排序结构。你可以用TreeMap或基数树逃脱（基数会为你节省一些空间）。这种开销将是排序操作或插入到已排序的数据结构中的开销。但是，一旦排序了二进制搜索，就会给你logN+1最坏情况的查找性能。

注Lucene的使用基数树据我所知

2013-01-10 22:07:55 Woot4Moo

我看了一下二分查找，但我不确定如何调整它，因此它会返回第一个条目“习惯”，因为如果我使用匹配字符串开头的比较函数，我会停下来击中任何比赛，而不是第一个。 – user1968240

您可以随时看Patricia Trees。他们几乎完全适合这种事情。

2013-01-10 22:08:56

A Trie是你在找什么。

2013-01-10 22:09:10

id靠向基数树，节省更多的空间 – Woot4Moo

你的帖子留下了太多的问题没有回答。我的解释是你想从一个无序的单词列表中创建一个字典。但是当你搜索ha时，你真正想要什么？

你想

如果你想1和/或3，那么谁说trie的人是正确的。（我给你的链接有一个易于阅读的实现）。

如果2是你想要的，那么你可以谈论一个用例吗？如果没有，那么你正在寻找使用string search algorithm。没有更多的细节，很难提供更精确的建议。

2013-01-10 22:52:18

你的问题有很多模糊的地方。根据您的要求，您可能会发现Rabin-Karp字符串搜索方法对您很有用。

2013-01-12 13:35:17 rossum

回答