Đếm số lần xuất hiện mẫu "1(0+)1" trong chuỗi bằng C++

Cho một chuỗi str chứa các ký tự 0, 1 và các chữ cái khác. Chuỗi cũng chứa các mẫu dạng "1(0+)1" trong đó 0+ có nghĩa là bất kỳ số lượng nào (>0) các số 0 liên tiếp. Mục tiêu là tìm các mẫu như vậy ("1(0+)1") bên trong chuỗi str.

Ví dụ

Đầu vào - str = "abb010bb10111011"

Đầu ra - Số lần xuất hiện mẫu "1(0+)1" trong chuỗi là 2

Giải thích - Các mẫu trong str đượchighlight: "abb010bb10111011", "abb010bb10111011"

Đầu vào - str = "01001011001001100"

Đầu ra - Số lần xuất hiện mẫu "1(0+)1" trong chuỗi là 4

Giải thích - Các mẫu trong str được highlight: 4 vị trí

Phương pháp sử dụng

Nhìn thấy tất cả các mẫu bắt đầu và kết thúc bằng 1. Ta đánh dấu 1 đầu tiên bằng biến cờ check = 1 và bỏ qua tất cả các 0.

Với bất kỳ ký tự khác (không phải 0 cũng không phải 1) đặt check = 0.

Nếu tìm thấy 1 khác và cờ check = 1 thì xem giá trị trước đó có phải 0 không. Nếu có thì tăng count vì 0 trước đó nằm giữa hai 1. Với ký tự không phải 0 hoặc 1, đặt lại check = 0. Lần gặp 1 tiếp theo sẽ được xem là bắt đầu mẫu mới (nếu có).

• Nhập chuỗi str
• Hàm Pattern_occurrences(string str, int length) trả về số mẫu
• Khởi tạo count = 0, cờ check = 0
• Duyệt str từ i=0 đến length-1
• Nếu str[i] == '1' và check == 1: nếu str[i-1] == '0' thì count++
• Nếu str[i] == '1' và check == 0: check = 1, continue
• Nếu str[i] không phải '0' cũng không phải '1': check = 0
• Trả về count

Chương trình minh họa

#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 << "Số lần xuất hiện mẫu \"1(0+)1\" trong chuỗi là: " << Pattern_occurrences(str, length);
    return 0;
}

Đầu ra

Số lần xuất hiện mẫu "1(0+)1" trong chuỗi là: 3