Chúng tôi được cung cấp với hai chuỗi str_1 và str_2 làm đầu vào. Mục đích là tìm số lượng các chuỗi giống như str_2 có thể được tạo bằng cách sử dụng các chữ cái được chọn từ str_1 mà từ đó mỗi ký tự chỉ được sử dụng một lần.
Lưu ý - Tất cả các bảng chữ cái trong cả hai đều ở trong cùng một trường hợp.
Hãy cho chúng tôi hiểu với các ví dụ.
Đầu vào - str_1 ="abcaaaabca", str_2 ="bca";
Đầu ra - Đếm số lần xuất hiện của một chuỗi có thể được xây dựng từ một chuỗi đã cho khác là:2
Giải thích - Các chuỗi con bca trong str_a -
str_1[1-3]=”bca” and str[7-9]=”bca”
Đầu vào - str_1 ="about", str_2 ="cout";
Đầu ra - Đếm số lần xuất hiện của một chuỗi có thể được xây dựng từ một chuỗi đã cho khác là - 0
Giải thích - Chuỗi con cout không có trong str_a.
Cách tiếp cận được sử dụng trong chương trình dưới đây như sau
Trước tiên, chúng tôi sẽ tính toán tần số của tất cả các bảng chữ cái trong str_1 và lưu trữ nó trong mảng arr_1 [26] và lưu trữ tần số của tất cả các bảng chữ cái trong arr_2 trong mảng arr_2 [26].
-
Lấy hai chuỗi str_1 và str_2. Tính độ dài dưới dạng str_1.size () vàstr_2.size ().
-
Hàm count_string (chuỗi str_1, int len_str_1, chuỗi str_2, int len_str_2) nhận cả chuỗi và độ dài và trả về một số chuỗi str_2 có thể được tạo từ str_1.
-
Lấy số lượng ban đầu là INT_MAX.
-
Khởi tạo hai mảng arr_1 [26] cho tần suất của các ký tự trong str_1 và arr_2 [26] cho tần suất của các ký tự trong arr_2 bằng 0.
-
Duyệt qua cả str_1 và str_2 bằng cách sử dụng vòng lặp for và tần số cập nhật trong arr_1 và arr_2.
-
Bây giờ duyệt arr_2 một lần nữa bằng cách sử dụng vòng lặp for và nếu tần số hiện tại arr_2 [i] khác 0 thì số đếm tối thiểu (giá trị trước đó) và arr_1 [i] / arr_2 [i] (lấy mỗi bảng chữ cái từ str_1 chỉ một lần cho mỗi ký tự của str_2) .
-
Cuối cùng, số đếm sẽ có giá trị nhỏ nhất là các ký tự tương ứng được so khớp của str_1 và str_2. ví dụ aaabbbb (a =3, b =4) và abb (a =1, b =2) tổng số tối thiểu sẽ là 1
-
Kết quả trả về ở cuối tất cả các vòng lặp là kết quả mong muốn.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
int count_string(string str_1, int length_str_1, string str_2, int length_str_2){
int count = INT_MAX;
int arr_1[26] = { 0 };
int arr_2[26] = { 0 };
for (int i = 0; i < length_str_1; i++){
arr_1[str_1[i] - 'a']++;
}
for (int i = 0; i < length_str_2; i++){
arr_2[str_2[i] - 'a']++;
}
int total_alphabets = 26;
for (int i = 0; i < total_alphabets; i++){
if(arr_2[i]){
count = min(count, arr_1[i] / arr_2[i]);
}
}
return count;
}
int main(){
string str_1 = "knowledge", str_2 = "know";
int length_str_1 = str_1.size();
int length_str_2 = str_2.size();
cout<<"Count occurrences of a string that can be constructed from another given string are: "<<count_string(str_1,length_str_1, str_2, length_str_2);
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 occurrences of a string that can be constructed from another given string are: 1