ค้นหารูปแบบทั้งหมดของ “1(0+)1” ในสตริงที่กำหนดใน C++

สมมติว่าสตริงมีรูปแบบเช่น 1(0+)1 โดยที่ (0+) หมายถึงการเกิดขึ้นต่อเนื่องกันของ 1 วินาทีที่ไม่ว่างเปล่า เราต้องหารูปแบบทั้งหมด รูปแบบสามารถทับซ้อนกันได้ สตริงไม่จำเป็นต้องเป็นสตริงไบนารี สามารถใส่ตัวเลขและตัวพิมพ์เล็กเท่านั้น สมมติว่าสตริงนั้นเหมือนกับ 1101001 แสดงว่ามีรูปแบบดังกล่าวสองรูปแบบ 101 และ 1001

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• วนซ้ำอักขระ c ทั้งหมดในสตริง

• เมื่อ c เป็น 1 เราจะวนซ้ำจนกว่าองค์ประกอบจะเป็น 0

• เมื่อสตรีม 0 จบ เราจะมาเช็คกันว่าตัวละครตัวต่อไปเป็น 1 หรือเปล่า

• ขั้นตอนเหล่านี้จะทำซ้ำจนกว่าจะถึงจุดสิ้นสุดของสตริง

ตัวอย่าง

#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