Số lần xuất hiện của mẫu “1 (0+) 1” trong một chuỗi trong C ++

Chúng ta được cung cấp một chuỗi str chứa 0s, 1s và các bảng chữ cái khác. Nó cũng chứa các mẫu có dạng “1 (0+) 1” trong đó 0+ nghĩa là bất kỳ số nào (> 0) trong 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.

Hãy cho chúng tôi hiểu với các ví dụ

Đầu vào - str =“abb010bb10111011”

Đầu ra - Số lần xuất hiện của mẫu “1 (0+) 1” trong một chuỗi là - 2

Giải thích - Các mẫu bên trong str được đánh dấu:“abb010bb10111011”, “abb010bb10111011”

Đầu vào - str =“01001011001001100”

Đầu ra - Số lần xuất hiện của mẫu “1 (0+) 1” trong một chuỗi là - 4

Giải thích - Các mẫu bên trong str được đánh dấu:“01001011001001100”, “01001011001001100”, “01001011001001100”, “01001011001001100”

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau

Có thể thấy rằng tất cả các mẫu đều bắt đầu và kết thúc bằng 1. Chúng tôi sẽ đánh dấu mẫu đầu tiên bằng cách sử dụng biến cờ check =1 và bỏ qua tất cả các số 0.

Đối với bất kỳ ký tự nào khác (không phải 0 hay 1), hãy đặt kiểm tra là 0.

Nếu chúng ta tìm thấy 1 khác và kiểm tra cờ là 1 thì hãy xem giá trị trước đó có phải là 0. Nếu có thì số gia tăng như 0 trước đó nằm giữa hai giá trị. Đối với bất kỳ bộ nào khác 0 hoặc 1, hãy kiểm tra lại bằng 0.

Lấy chuỗi đầu vào là str.
Hàm Pattern_occurrences (string str, int length) lấy chuỗi và độ dài của nó và trả về số lần xuất hiện của một mẫu “1 (0+) 1” trong một chuỗi
Lấy số lượng ban đầu là 0.
Ban đầu, hãy kiểm tra biến cờ là 0.
Đảo ngược str bằng vòng lặp for từ chỉ mục i =0 đến i
Nếu ký tự hiện tại str [i] là 1 và kiểm tra là 0 thì hãy đặt kiểm tra là 1 và tiếp tục.
Nếu ký tự hiện tại str [i] là 1 và kiểm tra là 1. Thì ký tự thứ hai là 1. Kiểm tra xem giá trị trước đó str [i-1] có phải là 0. Nếu có thì tìm thấy mẫu. Số lượng tăng dần.
Nếu ký tự hiện tại không phải là 0 hoặc 1 thì nó sẽ không bao giờ là một phần của mẫu. Đặt kiểm tra là 0. Bây giờ lần gặp tiếp theo 1 sẽ được coi là phần bắt đầu của mẫu tiếp theo (nếu tồn tại).
Ở cuối số đếm sẽ có một số mẫu như vậy bên trong str.
Kết quả là số lượt trả lại.

Ví dụ

#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<<"Count of occurrences of a “1(0+)1” pattern in a string are: "<< Pattern_occurrences(str, length);
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Count of occurrences of a “1(0+)1” pattern in a string are: 3