文字列内に正確に K 回現れる、長さ M の部分文字列の数を数えます。

この記事では、コンピューター サイエンスの分野におけるユニークで魅力的な問題、「文字列内でちょうど K 回出現する M 長の部分文字列を数える」について詳しく掘り下げていきます。この種の質問は、プログラミングコンテストや面接でよく聞かれます。始める前に、何を扱うのかを定義しましょう -

• サブストリング− 別の文字列内で見つかった連続シーケンス。

• M Length− 対象となる部分文字列の長さ。

• K 回 − 元の文字列内に部分文字列が出現する正確な回数。

アルゴリズムの説明

この問題を解決するために、ハッシュ マップ (C では順序なしマップとも呼ばれます) の機能を利用します。ハッシュ マップを使用すると、キーと値のペアの形式でデータを保存できるため、検索と挿入の操作に一定の時間の複雑さを提供できるため、このような問題を解決するための優れたツールになります。

文字列内にちょうど K 回現れる長さ M の部分文字列を計算するアルゴリズムは次のとおりです -

• 空のハッシュ マップを初期化します。

• 文字列を反復処理し、考えられるすべての M 長の部分文字列を作成します。

• 各部分文字列をハッシュ マップに追加します。すでに存在する場合は、その数を増やします。

• すべての部分文字列が計算されたら、ハッシュ マップを反復処理して、正確に K 回出現するすべての部分文字列を見つけます。

C実装

これは、上記のアルゴリズムの C 実装です -

＃＃＃例＃＃＃ リーリー ＃＃＃出力＃＃＃ リーリー

上記のコードでは、countSubstrings 関数は入力文字列 s、部分文字列の長さ M、および出現回数 K をパラメーターとして受け取ります。すべての部分文字列とその出現を追跡するために、順序なしマップ count_map を初期化します。次に、文字列を反復して長さ M の可能なすべての部分文字列を作成し、部分文字列ごとにマップ内のカウントをインクリメントします。すべての部分文字列が計算されると、マップを反復処理して、正確に K 回出現するすべての部分文字列を計算します。

main 関数はコードの実行を開始する場所です。文字列 s と M と K の値を初期化します。次に、countSubstrings 関数を呼び出し、結果を出力します。

テストケースの例

M=3、K=3 の文字列「abcabcabc」について考えてみましょう。

ここで、M 番目の長さの部分文字列は、「abc」、「bca」、「cab」、「abc」、「bca」、「cab」、「abc」です。明らかに、部分文字列「abc」は文字列内にちょうど 3 回出現するため、プログラムの出力は 1 になります。

ハッシュ マップを使用して部分文字列を計算するこの問題へのアプローチは、コンピューター サイエンスにおける時空間のトレードオフの良い例です。余分なスペースを使用して部分文字列とその数を保存すると、一定時間内の出現をカウントすることで問題の時間の複雑さを大幅に軽減できます。

時間と空間の複雑さ

このアルゴリズムの時間計算量は O(n) です。ここで、n は文字列の長さです。これは、文字列を 1 回だけ反復処理して、考えられる M 個の長さの部分文字列をすべて作成するためです。

ハッシュ マップのストレージ要件により、空間の複雑さも O(n) になります。最悪の場合、各部分文字列は一意となり、マップ内に n 個の異なるエントリが生成されます。

＃＃＃結論は＃＃＃

この記事では、コンピューター サイエンスにおける一般的な問題、つまり文字列内でちょうど K 回出現する M 長の部分文字列の数を数えることについて研究します。ハッシュ マップを使用して効率的なソリューションを C で実装しました。これにより、一定時間の検索と挿入操作が可能になりました。この問題は、データ構造とアルゴリズムを組み合わせて複雑な問題を効果的に解決する方法を示す完璧な例です。

以上が文字列内に正確に K 回現れる、長さ M の部分文字列の数を数えます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。