c++ - 快速字符串搜索？

Question

我有一个字符串向量，必须检查向量中的每个元素是否存在于给定的 5000 个单词列表中。除了两个嵌套循环的普通方法之外，在 C++ 中有没有更快的方法来做到这一点？

Answer 1

您应该将字符串列表放入std::set。它是一种针对搜索优化的数据结构。查找给定元素是否在集合中是一个比迭代所有条目快得多的操作。

当您已经在使用 C++11 时，您还可以使用std::unordered_set，它的查找速度更快，因为它是作为哈希表实现的。

这是否适用于学校/大学：准备好解释这些数据结构如何变得更快。当你的导师要求你解释为什么使用它们时，“网上有些人告诉我”不太可能让你在课本上贴上标签。

Answer 2

您可以将单词列表放在std::unordered_set中。然后，对于向量中的每个元素，您只需要测试它是否在 O(1) 中的 unordered_set 中。您将有一个 O(n) 的预期复杂度（查看评论以了解为什么它只是预期的）。

Answer 3

你可以对向量进行排序，然后你可以用一个“循环”来解决这个问题（假设你的字典也被排序了），这意味着 O(n) 不计入排序成本。

Answer 4

所以你有一个字符串向量，每个字符串都有一个或多个单词，你有一个字典向量，你应该确定字符串向量中的哪些单词也在字典中？字符串向量很烦人，因为您需要查看每个单词。我首先创建一个新向量，将每个字符串拆分为单词，然后将每个单词推入新向量。然后对新向量进行排序并通过std::unique算法运行以消除重复。然后对字典进行排序。然后运行两个范围std::set_intersection以写入结果。