単一の異なる文字で構成される部分文字列の数を数える

この記事では、特定の文字列内の単一の異なる文字で構成される部分文字列の数をカウントする問題について説明します。この問題を解決するための効率的なアルゴリズムを検討し、それを実装するための C コードを提供します。

文字列 S が与えられた場合、タスクは 1 つの異なる文字で構成される部分文字列の数をカウントすることです。

たとえば、入力文字列が「aaaaa」の場合、単一の異なる文字で構成される部分文字列が 15 個あるため、出力は 15 になるはずです。部分文字列は、「a」、「a」、「a」、「a」、「a」、「a」、「a」、「a」、「a」、「a」、「a」、「aaa」です。 、「ああ」、「ああ」、「ああ」、「ああ」。

この問題は線形時間計算量で解決できます。入力文字列を反復処理して、現在の文字と現在の部分文字列の長さを追跡できます。新しい文字に遭遇するか、文字列の終わりに達するたびに、現在の文字と現在の部分文字列の長さによって形成できる部分文字列の数をカウントできます。

この問題を解決するための段階的なアルゴリズムは次のとおりです -

• count と len を 1 に初期化します。

• 文字列 S をインデックス 1 から n-1 まで反復します。

• 現在の文字が前の文字と同じ場合、len は 1 増加します。

• 現在の文字が前の文字と異なる場合は、(len*(len 1))/2 をカウントに追加し、len を 1 にリセットします。

• カウントを返します。

• アルゴリズムを理解するために、文字列「aaaaa」を例に挙げてみましょう -

count と len を 1 に初期化します。

• 文字列をインデックス 1 から n-1 まで反復します:

• インデックス 1 では、現在の文字は前の文字と同じであるため、len は 1 増加します。

• インデックス 2 では、現在の文字は前の文字と同じであるため、len が 1 増加します。

• インデックス 3 では、現在の文字は前の文字と同じであるため、len が 1 増加します。

• インデックス 4 では、現在の文字は前の文字と同じであるため、len が 1 増加します。

• 文字列の終わりに達したので、(len*(len 1))/2 を追加してカウントします。カウント = カウント (5*(5 1))/2 = 15。

• カウントを返します。

• C実装

これは、上記のアルゴリズムを実装する C コードです -

この記事では、特定の文字列内の単一の異なる文字で構成される部分文字列の数をカウントする問題について説明しました。この問題を線形時間計算量で解決する効率的なアルゴリズムを提供し、C で実装します。この問題は他の手法を使用しても解決できますが、上記のアルゴリズムでは

以上が単一の異なる文字で構成される部分文字列の数を数えるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。