c++ - C++ を使用してファイル内のすべての繰り返しパターンを見つける

Question

入力ファイルで少なくとも 3 文字からなるすべての繰り返しシーケンスを見つけて、最も頻繁なものを出力する方法を探しています! 検索するパターンの最大サイズに上限がないため、多くの文字列処理と入力ファイルの集中的な検索が必要なようです!

最小限の処理と煩雑さでそれを行う効率的なアルゴリズムはありますか? string.h を使用する必要がありますか、それとも char 配列を使用したほうがよいでしょうか? 開始方法に関するヒント/役立つスニペットなどはありますか?

tnx

Answer 1

ファイルから接尾辞木を作成することをお勧めします。これにより、ファイルのサイズに関して線形の複雑さが生じ、問題が解決されます。アルゴリズムを少し変更して、文字列自体とは別に文字列が出会った回数を保存できます。これは、接尾辞木を作成する方法を説明するすばらしい投稿です。

Answer 2

最も頻繁なシーケンスの長さが 4 文字であることを理解していれば、最も頻繁なシーケンスを見つけるのは非常に簡単です。入力ファイルのサイズであるO(n)時間内に実行できます。n

を作成std::map<string,int>し、一度に 4 文字のシーケンスを取得して文字ごとに反復し、マップ内のそれぞれのキーで値をインクリメントできます。