นับจำนวนการเกิดขึ้นของสตริงที่สามารถสร้างจากสตริงที่กำหนดอื่นใน C++

เราได้รับสองสตริง str_1 และ str_2 เป็นอินพุต เป้าหมายคือการหาจำนวนสตริงที่เหมือนกับ str_2 ที่สามารถสร้างโดยใช้ตัวอักษรที่เลือกจาก str_1 ซึ่งแต่ละอักขระใช้เพียงครั้งเดียว

หมายเหตุ − ตัวอักษรทั้งหมดในทั้งสองตัวเป็นกรณีเดียวกัน

ให้เราเข้าใจด้วยตัวอย่าง

ป้อนข้อมูล − str_1 ="abcaaaabca", str_2 ="bca";

ผลผลิต − จำนวนการเกิดขึ้นของสตริงที่สามารถสร้างจากสตริงที่กำหนดอื่นได้คือ:2

คำอธิบาย − สตริงย่อย bca ใน str_a −

str_1[1-3]=”bca” and str[7-9]=”bca”

ป้อนข้อมูล − str_1 ="เกี่ยวกับ", str_2 ="cout";

ผลผลิต − นับจำนวนการเกิดขึ้นของสตริงที่สามารถสร้างจากสตริงที่กำหนดอื่นได้ − 0

คำอธิบาย − สตริงย่อยไม่มีอยู่ใน str_a

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

ก่อนอื่นเราจะคำนวณความถี่ของตัวอักษรทั้งหมดใน str_1 และเก็บไว้ในอาร์เรย์ arr_1[26] และเก็บความถี่ของตัวอักษรทั้งหมดใน arr_2 ในอาร์เรย์ arr_2[26]

• ใช้สองสตริง str_1 และ str_2 คำนวณความยาวเป็น str_1.size() andstr_2.size()

• ฟังก์ชัน count_string(string str_1, int len_str_1, string str_2, int len_str_2) รับทั้งสตริงและความยาว และคืนค่าจำนวนสตริง str_2 ที่สามารถสร้างได้จาก str_1

• นับเริ่มต้นเป็น INT_MAX

• เริ่มต้นสองอาร์เรย์ arr_1[26] สำหรับความถี่ของอักขระใน str_1 และ arr_2 [26] สำหรับความถี่ของอักขระใน arr_2 ด้วย 0

• สำรวจทั้ง str_1 และ str_2 โดยใช้ for loop และอัปเดตความถี่ใน arr_1 และ arr_2

• ตอนนี้สำรวจ arr_2 อีกครั้งโดยใช้ for loop และหากความถี่ปัจจุบัน arr_2[i] ไม่ใช่ศูนย์ให้นับขั้นต่ำ (ค่าก่อนหน้า) และ arr_1[i]/arr_2[i] ( รับตัวอักษรแต่ละตัวจาก str_1 เพียงครั้งเดียวสำหรับอักขระแต่ละตัวของ str_2 ) .

• ในท้ายที่สุด การนับจะมีค่าต่ำสุดของอักขระที่เกี่ยวข้องกันของ str_1 และ str_2 ตัวอย่าง aaabbbb (a=3,b=4) และ abb(a=1,b=2) จำนวนขั้นต่ำจะเป็น 1

• นับกลับเมื่อสิ้นสุดลูปทั้งหมดเป็นผลลัพธ์ที่ต้องการ

ตัวอย่าง

#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;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count occurrences of a string that can be constructed from another given string are: 1