我正在寻找一种方法来查找输入文件中至少包含 3 个字符的所有重复序列,然后打印出最常见的序列!它似乎需要大量的字符串处理和对输入文件的密集搜索,特别是因为要查找的模式的最大大小没有上限!
是否有任何有效的算法可以以尽可能少的处理和混乱来做到这一点?我应该使用 string.h 还是使用 char 数组会更好?关于如何开始的任何提示/有用的片段等?
tnx
我建议您从文件中创建一个后缀树。这将具有相对于文件大小的线性复杂性,并将解决问题。您可以稍微修改算法以存储字符串与字符串本身相分离的次数。这是一篇很棒的文章,解释了如何创建后缀树。
如果您意识到最频繁的序列是 4 个字符长,那么找到最频繁的序列非常容易。它可以及时完成,输入文件的大小在O(n)
哪里。n
您可以构建一个std::map<string,int>
,逐个字符地迭代,一次获取 4 个字符的序列,并使用映射中的相应键递增值。