Đếm chuỗi con của một chuỗi nhị phân chứa K cái trong C ++

Chúng tôi được cung cấp một chuỗi số nhị phân, tức là sự kết hợp của 0’s và 1’s và một giá trị nguyên k và nhiệm vụ là tính số chuỗi con được tạo thành với chuỗi nhị phân đã cho có k 1’s.

Đầu vào - chuỗi str =‘10000100000’, k =2

Đầu ra - Đếm chuỗi con của một chuỗi nhị phân chứa K là - 6

Giải thích - Các chuỗi con có thể được tạo thành từ chuỗi đã cho là 1, 10, 100, 1000, 10000, 010, 100001, 10001, 1001, 101, 11, 1000010. Vậy có 6 chuỗi con có k số 1 tức là đúng 2 số.

Đầu vào - chuỗi str =‘10000100000’, k =3

Đầu ra - Số chuỗi con của một chuỗi nhị phân chứa K là - 0

Giải thích - Chúng ta được cho với một giá trị nguyên của k là 3 và nếu chúng ta kiểm tra chuỗi chứa số nhị phân của chúng ta, nó chỉ có 2 đơn vị. Vì vậy, không có khả năng xảy ra chuỗi con có k số đơn vị.

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

• Nhập một chuỗi số nhị phân có kết hợp của 0 và 1 và một biến số nguyên k.

• Tính độ dài của chuỗi bằng cách sử dụng hàm length () và chuyển dữ liệu cho hàm để xử lý thêm.

• Khai báo số lượng biến tạm thời và tổng là 0 để lưu trữ các chuỗi con có k chuỗi.

• Khai báo một mảng để lưu trữ tần số của các tần số có kích thước bằng độ dài của chuỗi cộng với một và khởi tạo nó bằng 0 và đặt phần tử đầu tiên của mảng là 1.

• Bắt đầu vòng lặp FOR từ 0 cho đến hết chiều dài của một mảng

• Bên trong vòng lặp, đặt tổng là tổng + str [i] - ‘0’. Kiểm tra IF tổng> =k rồi đặt số đếm là count + arr [total-k].

• Số lần trả lại

• In kết quả.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
int sub_k_ones(string str, int length, int k){
   int count = 0;
   int total_1 = 0;
   int arr_fre[length + 1] = {0};
   arr_fre[0] = 1;
   for (int i = 0; i < length; i++){
      total_1 = total_1 + (str[i] - '0');
      if (total_1 >= k){
         count = count + arr_fre[total_1 - k];
      }
      arr_fre[total_1]++;
   }
   return count;
}
int main(){
   string str = "10000100000";
   int length = str.length();
   int k = 2;
   cout<<"Count of substrings of a binary string containing K ones are: "<<sub_k_ones(str, length, k) << endl;
   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 substrings of a binary string containing K ones are: 6