เขียนโปรแกรม C++ เพื่อนับจำนวน substring ที่เริ่มด้วย '1' และจบด้วย '1'

สมมติว่าเรามีความยาวของสตริง 'str' และสตริง งานคือนับจำนวน substring ที่เริ่มด้วย '1' และจบด้วย '1' ใน Binary String ที่กำหนด Binary String มี '1' และ '0' เท่านั้น ตัวอย่างเช่น

ตัวอย่างอินพุต 1

N = 5, str = '11101'

เอาต์พุต

6

คำอธิบาย

ใน Binary String ที่กำหนด เรามี 6 substrings ที่เริ่มด้วย '1' และจบด้วย '1' เซตของ substring เหล่านี้คือ {'11', '111', '1110', '11101', '1101', '101'}

ตัวอย่างอินพุต 2

N = 4, str = '0011'

เอาต์พุต

1

คำอธิบาย

ใน Binary String ที่กำหนด เรามี 1 substring ที่เริ่มด้วย '1' และจบด้วย '1' เซตของ substring นี้เป็น singleton set คือ {'11'}

วิธีการแก้ปัญหา

สำหรับสตริงที่กำหนด เราต้องนับจำนวน substring ที่เริ่มด้วย '1' และจบด้วย '1' ปัญหานี้คล้ายกับปัญหา Handshake problem ที่รู้จักดี ซึ่งเราต้องนับจำนวนการจับมือในงานเลี้ยงของ 'n' คน

ถ้าเรานับจำนวน '1' ในสตริงที่กำหนด เราสามารถหาเซตของ substring ที่เริ่มด้วย '1' และจบด้วย '1' ได้

• รับอินพุตสตริงความยาว N
• ฟังก์ชัน Integer countSubstring(int N, string s) รับความยาวของสตริงและสตริงเป็นอินพุตและคืนค่าจำนวน substring ทั้งหมดที่เริ่มด้วย '1' และจบด้วย '1'
• วนลูปผ่านสตริงทั้งหมดและนับจำนวน '1' ในสตริง
• นับจำนวน substring (คู่) ในสตริงที่กำหนดโดย n*(n-1)/2
• คืนค่าผลลัพธ์ของ n*(n-1)/2

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

#include <iostream>
using namespace std;

int countSubstring(int N, string s) {
    int count = 0;
    for (int i = 0; s[i] != '\0'; ++i) {
        if (s[i] == '1')
            count++;
    }
    return count * (count - 1) / 2;
}

int main() {
    int N = 5;
    string str = "11101";
    cout << countSubstring(N, str) << endl;
    return 0;
}

ผลลัพธ์

ถ้าเราจะรันโค้ดด้านบน จะพิมพ์เอาต์พุตเป็น

6

เนื่องจากจำนวน '1' ที่มีอยู่ในสตริงที่กำหนดคือ '4' นั่นคือ count = 4 จำนวน substring ทั้งหมดที่เริ่มด้วย '1' และจบด้วย '1' คือ 4*(4-1)/2 = 6