Giả sử chúng ta đã cung cấp độ dài của chuỗi ‘str’ và một chuỗi. Nhiệm vụ là đếm số chuỗi con bắt đầu bằng ‘1’ và kết thúc bằng ‘1’ trong một Chuỗi nhị phân nhất định. Chuỗi nhị phân chỉ chứa ‘1’ và ‘0’. Ví dụ:
Đầu vào-1 -
N = 5 str = ‘11101’
Đầu ra -
6
Giải thích - Trong Chuỗi nhị phân đã cho, ta có 6 chuỗi con bắt đầu bằng ‘1’ và kết thúc bằng ‘1’. Tập hợp các chuỗi con này là {‘11’, ‘111’, ‘1110’, ‘11101’, ‘1101’, ‘101’}.
Đầu vào-1 -
N = 4 str = ‘0011’
Đầu ra -
1
Giải thích -
Trong Chuỗi nhị phân đã cho, chúng ta có 1 chuỗi con bắt đầu bằng ‘1’ và kết thúc bằng ‘1’. Tập hợp các chuỗi con này là một tập hợp đơn lẻ, tức là {‘11 ’}.
Phương pháp được sử dụng để giải quyết vấn đề này
Đối với chuỗi đã cho, chúng ta phải đếm số chuỗi con bắt đầu bằng ‘1’ và kết thúc bằng ‘1’. Bài toán tương tự như bài toán Bắt tay nổi tiếng, trong đó chúng ta phải đếm số lần bắt tay trong một nhóm gồm ‘n’ người.
Nếu chúng ta đếm số lượng 1 trong chuỗi đã cho, thì chúng ta có thể tìm thấy tập hợp các chuỗi con bắt đầu bằng ‘1’ và kết thúc bằng ‘1’.
-
Lấy Đầu vào một chuỗi có độ dài N.
-
Một hàm Integer countSubstring (int N, string s) lấy độ dài của chuỗi và một chuỗi làm đầu vào và trả về tổng số của tất cả các chuỗi con bắt đầu bằng ‘1’ và kết thúc bằng ‘1’.
-
Lặp lại toàn bộ chuỗi và đếm số không. của ‘1’ trong chuỗi.
-
Đếm số không. của chuỗi con (cặp) trong chuỗi đã cho bởi n * (n-1) / 2.
-
Trả về kết quả là n * (n-1) / 2.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên thì nó sẽ in đầu ra là,
6
Vì số lượng '1 có trong chuỗi đã cho là' 4 ', tức là count =4, tổng số chuỗi con bắt đầu bằng' 1 'và kết thúc bằng' 1 'là, 4 * (4-1) / 2 =6.