Chúng ta được cung cấp một chuỗi str [] và một ký tự X. Mục đích là tìm các chuỗi con của str [] sao cho tất cả các chuỗi con chứa X ít nhất một lần. Đối với str [] =”abc '' và X =’ a ’, các chuỗi con chứa‘ a ’ít nhất một lần là“ a ”,“ ab ”,“ abc ”. Số lượng là 3.
Hãy cho chúng tôi hiểu với các ví dụ.
Đầu vào - str [] =“aabccd” X =’c’
Đầu ra - Số chuỗi con có chứa ký tự X ít nhất một lần là - 14
Giải thích - Các chuỗi con chứa ít nhất một chữ 'c' sẽ là:“c”, “c”, “bc”, “cc”, “cd”, “abc”, “bcc”, “ccd”, “aabc”, “ abcc ”,“ bccd ”,“ aabcc ”,“ abccd ”,“ aabccd ”.
Đầu vào - str [] =“cài đặt” X =’s’
Đầu ra - Số chuỗi con có chứa ký tự X ít nhất một lần là - 14
Giải thích - Các chuỗi con chứa ít nhất một 's' sẽ là:“s”, “s”, “se”, “gs”, “set”, “ngs”, “setting”, “ings”, “setti”, “ tings ”,“ settin ”,“ ttings ”,“ setting ”,“ ettings ”,“ settings ”
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Theo cách tiếp cận này, chúng ta biết rằng tổng số chuỗi con của chuỗi có n ký tự là n * (n + 1) / 2.
Bây giờ chúng ta sẽ duyệt qua chuỗi và đếm các ký tự trước ký tự X dưới dạng tạm thời. Ngay sau khi gặp X, các chuỗi chứa X sẽ có độ dài temp + 1. Bây giờ chúng ta có X số chuỗi con chứa X sẽ là các ký tự còn lại (chỉ số độ dài-hiện tại) X (temp + 1). Thêm cái này để đếm. Bây giờ cập nhật temp =0 và tiếp tục cho X tiếp theo cho đến cuối chuỗi. Cuối cùng, chúng tôi đếm là số chuỗi con có chứa ký tự X ít nhất một lần.
-
Lấy một chuỗi str và một ký tự x.
-
Hàm sub_x (char str [], int length, char x) nhận một chuỗi, đó là độ dài, ký tự x và trả về số lượng các chuỗi con chứa ký tự x ít nhất một lần.
-
Lấy số lượng ban đầu là 0. Lấy tạm thời là các ký tự trước x đầu tiên trong str [] là 0 ban đầu.
-
Lấy kích thước đếm ban đầu * (size + 1) / 2 cho số tất cả các chuỗi con có thể có của str [].
-
Traverse str [] bằng cách sử dụng vòng lặp for từ i =0 đến i
-
Nếu str [i] không phải là x thì tốc độ tăng dần là các ký tự trước x đầu tiên.
-
Nếu str [i] ==x thì độ dài của chuỗi bao gồm x sẽ là temp + 1. Các ký tự còn lại của str [] sẽ là length-i.
-
Tất cả các chuỗi con sẽ là (temp + 1) * (length-i). Thêm cái này để đếm. Bây giờ hãy cập nhật temp =0 cho lần lặp tiếp theo.
-
Làm điều này cho đến khi đạt đến cuối str [].
-
Kết quả trả về là kết quả cuối cùng.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int sub_x(string str, int length, char x){
int count = 0;
int temp = 0;
for (int i = 0; i < length; i++){
if (str[i] == x){
int temp_2 = temp + 1;
count = count + temp_2 * (length - i);
temp = 0;
}
else{
temp++;
}
}
return count;
}
int main(){
string str = "abcabbc";
int length = str.length();
char x = 'a';
cout<<"Count of sub-strings that contain character X at least once are: "<<sub_x(str, length,
x);
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 sub-strings that contain character X at least once are: 19