【C++】文字列内の「1(0+)1」パターンの出現回数を数える方法

問題概要

0、1、およびその他の英字を含む文字列 str が与えられます。この文字列には「1(0+)1」という形式のパターンが含まれていることがあります。ここで「0+」は、1個以上の連続する0を意味します。この記事の目的は、文字列 str 内にこのパターンが何回出現するかを数えることです。

入出力例

例1

• 入力 − str = "abb010bb10111011"
• 出力 − 「1(0+)1」パターンの出現回数： 2
• 説明 − パターンに該当するのは "101" と "101" の2箇所です。

例2

• 入力 − str = "01001011001001100"
• 出力 − 「1(0+)1」パターンの出現回数： 4
• 説明 − パターンに該当するのは "1001"、"101"、"1001"、"1001" の4箇所です。

アルゴリズムの考え方

すべてのパターンは必ず「1で始まり、1で終わる」という性質を利用します。最初に現れた1をフラグ変数 check=1 で記録し、その後の0はすべてスキップします。0と1以外の文字が出てきた場合は、check を0に戻します。別の1が見つかり、かつ check が1の状態であるとき、直前の文字が0であれば、その0が2つの1に挟まれていることを意味するため、カウントを1増やします。

手順の詳細

1. 入力として文字列 str を受け取ります。
2. 関数 Pattern_occurrences(string str, int length) は、文字列とその長さを受け取り、「1(0+)1」パターンの出現回数を返します。
3. カウント用変数 count を0で初期化します。
4. フラグ変数 check を0で初期化します。
5. forループを使用し、インデックス i=0 から i<length まで文字列を走査します。
6. 現在の文字 str[i] が '1' であり、check が0の場合は、check を1に設定して次の文字へ進みます。
7. 現在の文字 str[i] が '1' であり、check が1の場合、これは2つ目の1です。直前の文字 str[i-1] が '0' であればパターンが見つかったことになるため、count を1増やします。
8. 現在の文字が0でも1でもない場合、その文字はパターンの一部になり得ないため、check を0に戻します。これにより、次に出現する1が次のパターン（存在する場合）の開始点として扱われます。
9. 走査が完了した時点で、count には文字列 str 内のパターンの総数が格納されています。
10. 結果として count を返します。

このアルゴリズムは文字列を一度だけ走査するため、時間計算量は O(n)、追加のメモリ使用量は O(1) と非常に効率的です。

サンプルコード

#include<iostream>
using namespace std;
int Pattern_occurrences(string str, int length){
    int count = 0;
    bool check = 0;
    for (int i = 0; i < length ; i++){
       if (str[i] == '1' && check == 1){
          if (str[i - 1] == '0'){
             count++;
          }
       }
       if (str[i] == '1' && check == 0){
          check = 1;
          continue;
       }
       if (str[i] != '0' && str[i] != '1'){
          check = 0;
       }
    }
    return count;
}
int main(){
    string str = "01010111011";
    int length = str.length();
    cout<<"文字列内の「1(0+)1」パターンの出現回数： "<< Pattern_occurrences(str, length);
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

文字列内の「1(0+)1」パターンの出現回数： 3