c++ - 在 txt 文件中查找长度为 L 的特定字符串的出现

Question

假设我有一个y长度为 N 的十六进制字符串，形式为y{N}y{N-1}...y{1}。然后给定另一个x长度为 L 的十六进制字符串（L 小于 N），我想检查这个字符串出现了多少次（如果有的话）y......比如说y{N}...x{L}x{L-1}...x{1}...y{j}..x{L}x{L-1}...x{1}....y{1}. 在 C++ 中执行此操作的最有效方法是什么？...我需要一个非常有效的实现，因为我想为大型数据库运行它

Answer 1

您的请求是一个简单的字符串搜索算法。有很多算法可以做到这一点。他们中的大多数会在 O(L+N) 中通过预处理给你一个很好的答案。

您还可以使用后缀树，它会在 O(L + Z) 中提供更快的答案，其中 Z 是 x 在 y 中出现的次数。后缀树虽然占用大量内存空间 (O(N²))，但在这里可能不是理想的选择。

Answer 2

“十六进制”在这里并不意味着什么。C++ 是一种计算机语言，并且适用于位。“十六进制”只是将 4 位组合在一起以供人类使用的便捷方式。

类似地，C++ 不会像y{N}y{N-1}...y{1}. 它将它们索引为y[0],y[1],y[N-1]. （没有y[N]。）

在正常情况下，std::string::find它会比你的磁盘快，这意味着它已经足够快了。

Answer 3

在 C++ 中，哪种方法最有效？

尝试您std::search的std::istream_iterator输入文件，如下所示：

#include <string>
#include <iterator>
#include <iostream>
#include <algorithm>

int main () {
  // std::ifstream input("input.txt");
  std::istream& input(std::cin);
  std::string search_for("1234");

  std::istream_iterator<char> last;
  std::istream_iterator<char> it(input);
  int count(0);

  while((it = std::search(it, last, search_for.begin(), search_for.end())) != last) {
    count++;
  }

  std::cout << count << "\n";

}

如果这还不够快，您可以尝试std::istreambuf_iterator.

如果这还不够快，您可以尝试对文件进行内存映射并使用初始和最终指针作为迭代器。