Giả sử một chuỗi có các mẫu như 1 (0+) 1. Trong đó (0+) cho biết các lần xuất hiện liên tiếp không trống của 1s. Chúng tôi phải tìm tất cả các mẫu. Các mẫu có thể chồng lên nhau. Chuỗi không nhất thiết phải là một chuỗi nhị phân. Nó chỉ có thể chứa các chữ số và ký tự viết thường. Giả sử chuỗi giống như 1101001, sau đó có hai mẫu như vậy. 101 và 1001.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Lặp lại tất cả ký tự c trong chuỗi
-
Khi c là 1, thì chúng ta lặp lại cho đến khi phần tử bằng 0
-
Khi luồng 0 kết thúc, chúng tôi sẽ kiểm tra xem ký tự tiếp theo có phải là 1 hay không
-
Các bước này sẽ được lặp lại cho đến khi đạt đến cuối chuỗi.
Ví dụ
#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);
} Đầu ra
Number of substrings of pattern 1(0+)1 is: 4