จำนวนครั้งที่พบรูปแบบ "1(0+)1" ในสตริงใน C++

เราได้รับสตริง str ที่มี 0, 1 และตัวอักษรอื่นๆ มันยังมีรูปแบบแบบ "1(0+)1" โดยที่ 0+ หมายถึงจำนวนใดๆ (>0) ของ 0 ที่ติดกัน เป้าหมายคือหารูปแบบเช่น ("1(0+)1") ภายในสตริง str

ตัวอย่าง

อินพุต - str = "abb010bb10111011"

เอาต์พุต - จำนวนครั้งที่พบรูปแบบ "1(0+)1" ในสตริงคือ - 2

คำอธิบาย - รูปแบบภายใน str ถูกไฮไลท์: "abb010bb10111011", "abb010bb10111011"

อินพุต - str = "01001011001001100"

เอาต์พุต - จำนวนครั้งที่พบรูปแบบ "1(0+)1" ในสตริงคือ - 4

คำอธิบาย - รูปแบบภายใน str ถูกไฮไลท์: "01001011001001100", "01001011001001100", "01001011001001100", "01001011001001100"

แนวทางที่ใช้ในโปรแกรมด้านล่าง

เห็นได้ว่ารูปแบบทั้งหมดเริ่มและจบด้วย 1 เราจะทำเครื่องหมาย 1 ตัวแรกโดยใช้ตัวแปร flag check=1 และข้าม 0 ทั้งหมด

สำหรับตัวอักษรอื่นๆ (ไม่ใช่ 0 และไม่ใช่ 1) ตั้ง check เป็น 0

ถ้าเราพบ 1 อีกตัวและ flag check เป็น 1 แล้ว ดูว่าค่าก่อนหน้าเป็น 0 หรือไม่ ถ้าใช่ ให้เพิ่ม count เพราะ 0 ก่อนหน้านั้นอยู่ระหว่าง 1 สองตัว สำหรับค่าที่ไม่ใช่ 0 หรือ 1 ตั้ง check อีกครั้งเป็น 0 ตอนนี้ 1 ตัวถัดไปที่พบจะถูกพิจารณาเป็นจุดเริ่มต้นของรูปแบบถัดไป (ถ้ามี)

• รับสตริงอินพุตเป็น str
• ฟังก์ชัน Pattern_occurrences(string str, int length) รับสตริงและความยาว คืนค่าจำนวนครั้งที่พบรูปแบบ "1(0+)1" ในสตริง
• ตั้งค่า count เริ่มต้นเป็น 0
• ใช้ตัวแปร flag check เป็น 0 เริ่มต้น
• เดินทางผ่าน str โดยใช้ลูป for จากดัชนี i=0 ถึง i
• ถ้าตัวอักษรปัจจุบัน str[i] เป็น 1 และ check เป็น 0 ตั้ง check เป็น 1 และ continue
• ถ้าตัวอักษรปัจจุบัน str[i] เป็น 1 และ check เป็น 1 แล้วเป็น 1 ตัวที่สอง ตรวจสอบว่าค่าก่อนหน้า str[i-1] เป็น 0 หรือไม่ ถ้าใช่ พบรูปแบบ เพิ่ม count
• ถ้าตัวอักษรปัจจุบันไม่ใช่ 0 และไม่ใช่ 1 มันจะไม่เคยเป็นส่วนหนึ่งของรูปแบบ ตั้ง check เป็น 0 ตอนนี้ 1 ตัวถัดไปที่พบจะถูกพิจารณาเป็นจุดเริ่มต้นของรูปแบบถัดไป (ถ้ามี)
• ที่สิ้นสุด count จะมีจำนวนรูปแบบเช่นนั้นภายใน str
• คืนค่า count เป็นผลลัพธ์

ตัวอย่างโค้ด

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

เอาต์พุต

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