c++ - 最好的字符串搜索算法

Question

我有一个代码，我在其中比较大数据，比如网页的来源与文件中的某些单词。要使用的最佳算法是什么？

可能有两种情况:

1. 如果我有大量的词要与源进行比较，在这种情况下，对于普通的字符串搜索算法，它必须取一个词，与数据进行比较，然后取下一个并与数据等等，直到全部完成。

2. 我的文件只有几个词，正常的字符串搜索就可以了，但还是要尽量减少时间。

什么算法最好？我知道 Boyer-Moore 和 Rabin-Karp 搜索算法。虽然Boyer-Moore搜索看起来很快，但我也想知道其他算法的名称和比较。

Answer 1

在这两种情况下，我认为您可能想要构建一个 patricia trie(也称为基数树)。最重要的是，查找时间为 O(k)，其中 k 是 trie 中字符串的最大长度。