c++ - 使用 C++ 查找文件中的所有重复模式

Question

我正在寻找一种方法来查找输入文件中至少包含 3 个字符的所有重复序列，然后打印出最常见的序列！它似乎需要大量的字符串处理和对输入文件的密集搜索，特别是因为要查找的模式的最大大小没有上限！

是否有任何有效的算法可以以尽可能少的处理和混乱来做到这一点？我应该使用 string.h 还是使用 char 数组会更好？关于如何开始的任何提示/有用的片段等？

tnx

Answer 1

我建议您从文件中创建一个后缀树。这将具有相对于文件大小的线性复杂性，并将解决问题。您可以稍微修改算法以存储字符串与字符串本身相分离的次数。这是一篇很棒的文章，解释了如何创建后缀树。

Answer 2

如果您意识到最频繁的序列是 4 个字符长，那么找到最频繁的序列非常容易。它可以及时完成，输入文件的大小在O(n)哪里。n

您可以构建一个std::map<string,int>，逐个字符地迭代，一次获取 4 个字符的序列，并使用映射中的相应键递增值。