この記事では、コンピューター サイエンスの分野におけるユニークで魅力的な問題、「文字列内でちょうど K 回出現する M 長の部分文字列を数える」について詳しく掘り下げていきます。この種の質問は、プログラミングコンテストや面接でよく聞かれます。始める前に、何を扱うのかを定義しましょう -
サブストリング− 別の文字列内で見つかった連続シーケンス。
M Length− 対象となる部分文字列の長さ。
K 回 − 元の文字列内に部分文字列が出現する正確な回数。
この問題を解決するために、ハッシュ マップ (C では順序なしマップとも呼ばれます) の機能を利用します。ハッシュ マップを使用すると、キーと値のペアの形式でデータを保存できるため、検索と挿入の操作に一定の時間の複雑さを提供できるため、このような問題を解決するための優れたツールになります。
文字列内にちょうど K 回現れる長さ M の部分文字列を計算するアルゴリズムは次のとおりです -
空のハッシュ マップを初期化します。
文字列を反復処理し、考えられるすべての M 長の部分文字列を作成します。
各部分文字列をハッシュ マップに追加します。すでに存在する場合は、その数を増やします。
すべての部分文字列が計算されたら、ハッシュ マップを反復処理して、正確に K 回出現するすべての部分文字列を見つけます。
これは、上記のアルゴリズムの C 実装です -
###例### リーリー ###出力### リーリーテストケースの例
M=3、K=3 の文字列「abcabcabc」について考えてみましょう。
ハッシュ マップを使用して部分文字列を計算するこの問題へのアプローチは、コンピューター サイエンスにおける時空間のトレードオフの良い例です。余分なスペースを使用して部分文字列とその数を保存すると、一定時間内の出現をカウントすることで問題の時間の複雑さを大幅に軽減できます。
時間と空間の複雑さ
このアルゴリズムの時間計算量は O(n) です。ここで、n は文字列の長さです。これは、文字列を 1 回だけ反復処理して、考えられる M 個の長さの部分文字列をすべて作成するためです。
この記事では、コンピューター サイエンスにおける一般的な問題、つまり文字列内でちょうど K 回出現する M 長の部分文字列の数を数えることについて研究します。ハッシュ マップを使用して効率的なソリューションを C で実装しました。これにより、一定時間の検索と挿入操作が可能になりました。この問題は、データ構造とアルゴリズムを組み合わせて複雑な問題を効果的に解決する方法を示す完璧な例です。
以上が文字列内に正確に K 回現れる、長さ M の部分文字列の数を数えます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。