【C++】文字列内の「1(0+)1」パターンをすべて検出する方法

文字列の中に「1(0+)1」という形式のパターンが含まれていると仮定します。ここで「(0+)」は、1個以上の「0」が連続して現れることを意味します。この記事では、文字列からこのパターンをすべて検出する方法を解説します。パターン同士が重なり合う場合もカウントの対象とします。なお、対象の文字列はバイナリ文字列であるとは限らず、数字と小文字の英字のみで構成された文字列を扱います。

例として、文字列が「1101001」の場合を考えてみましょう。この場合、「101」と「1001」の2つのパターンが見つかります。

解決のためのアプローチ

この問題は、以下の手順に従って解くことができます。

• 文字列内のすべての文字cを先頭から順に走査します。

• 現在の文字が「0」で、直前の文字が「1」だった場合は、「0」が続く限り読み進めます。

• 「0」の連続が終わった時点で、その次の文字が「1」かどうかを確認します。「1」であればパターンが成立したものとしてカウントします。

• これらの手順を文字列の末尾に到達するまで繰り返します。

C++による実装例

#include<iostream>
using namespace std;
int countBinPattern(string main_str) {
    char last_char = main_str[0];
    int i = 1, counter = 0;
    while (i < main_str.size()) {
        if (main_str[i] == '0' && last_char == '1') {
            while (main_str[i] == '0')
                i++;
            if (main_str[i] == '1')
                counter++;
        }
        last_char = main_str[i];
        i++;
    }
    return counter;
}
int main() {
    string str = "10010110000101";
    cout << "Number of substrings of pattern 1(0+)1 is: " << countBinPattern(str);
}

実行結果

Number of substrings of pattern 1(0+)1 is: 4

コードの解説

この実装では、変数last_charで直前の文字を記憶しながら文字列を1文字ずつ走査します。現在の文字が「0」で直前の文字が「1」のとき、内部ループによって「0」の連続を一気にスキップし、連続が終わった位置の文字が「1」であればカウンタをインクリメントします。この仕組みにより、互いに重なり合うパターンも漏れなく数え上げることができます。

入力文字列「10010110000101」の場合、「1001」「101」「100001」「101」の4つのパターンが検出され、実行結果は4となります。