Chương trình C++ tìm tất cả mẫu "1(0+)1" trong chuỗi

Cho chuỗi có mẫu 1(0+)1, trong đó (0+) là chuỗi 0 không rỗng liên tiếp. Tìm tất cả mẫu, có thể chồng chéo. Chuỗi không nhất thiết nhị phân, chỉ chứa chữ số và chữ thường. Ví dụ "1101001" → 2 mẫu: 101 và 1001.

Giải pháp: duyệt ký tự. Gặp '1' thì lặp qua các '0' liên tiếp. Khi hết chuỗi 0, kiểm tra ký tự tiếp có phải '1' không. Lặp đến hết chuỗi.

Ví dụ mã nguồn

#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);
}

Kết quả đầu ra

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