แบบสอบถามความถี่ของอักขระในสตริงย่อยใน C++

ในปัญหานี้ เราได้รับสตริง และคิวรี Q แต่ละอันมีเลขจำนวนเต็มสองตัว l และ r และอักขระ ch งานของเราคือการสร้างโปรแกรมเพื่อแก้ปัญหาการสืบค้นความถี่ของอักขระในสตริงย่อยใน C ++

คำอธิบายปัญหา :ที่นี่สำหรับแต่ละแบบสอบถาม เราจะพบความถี่ของการเกิดอักขระ 'ch' ในสตริงย่อย str[l...r]

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

str = “tutorialspoint”
Q = 2
0 6 t
5 13 i

ผลลัพธ์

2 2

คำอธิบาย

สำหรับคำถาม 1 − สตริงย่อยคือ “tutoria” อักขระ t ปรากฏ 2 ครั้ง

สำหรับข้อความค้นหา 2 − สตริงย่อยคือ “ialspoint” อักขระ i ปรากฏขึ้น 2 ครั้ง

แนวทางการแก้ปัญหา

วิธีที่ง่ายและตรงไปตรงมาในการแก้ปัญหาคือการข้ามผ่านสตริงจาก l ถึง r สำหรับแต่ละ querry และนับการเกิดขึ้นของอักขระ ch ในสตริง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

struct Query{
   int l, r;
   char ch;
};
int CalcCharFreq(string str, Query queries){
   int count = 0;
   for(int i = queries.l; i < queries.r; i++){
      if(str[i] == queries.ch )
      count++;
   }
   return count;
}

int main(){
   string str = "tutorialspoint";
   int Q = 2;
   Query queries[Q];
   queries[0].l = 0;
   queries[0].r = 5;
   queries[0].ch = 't';
   queries[1].l = 5;
   queries[1].r = 13;
   queries[1].ch = 'i';
   for(int i = 0; i<Q; i++)
   cout<<"For Query "<<(i+1)<<": The frequency of occurrence of character '"<<queries[i].ch<<"' is "<<CalcCharFreq(str, queries[i])<<"\n";
   return 0;
}

ผลลัพธ์

For Query 1: The frequency of occurrence of character 't' is 2
For Query 2: The frequency of occurrence of character 'i' is 2

แนวทางอื่น การแก้ปัญหาคือการใช้อาร์เรย์ที่คำนวณล่วงหน้า ที่นี่ เราจะสร้างอาร์เรย์ 2 มิติที่จะเก็บความถี่ของอักขระไม่เกินดัชนีที่ระบุ เช่น freq[3][2] จะเก็บความถี่ของอักขระ 'c' ที่ดัชนี 2 ในขั้นต้น ความถี่ทั้งหมดจะเป็น 0

จากนั้น เราจะคำนวณความถี่ของอักขระล่วงหน้าที่ค่าดัชนีทุกค่า หลังจากนั้นเราจะหาความถี่ของอักขระในช่วงนั้นโดยลบความถี่ของการเกิดที่ดัชนี l ออกจากที่ดัชนี r

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
int charFreq[100][26];

struct Query{
   int l, r;
   char ch;
};

void countCharFreq(string str, int size){

   memset(charFreq, 0, sizeof(int));
   for (int i = 0; i < size; i++){
      charFreq[i][str[i] - 'a']++;
   }
   for (int i = 1; i < size; i++) {
      for (int j = 0; j < 26; j++)
      charFreq[i][j] += charFreq[i - 1][j] ;
   }
}


int CalcCharFreq(Query queries){
   return charFreq[queries.r][queries.ch - 'a'] - charFreq[queries.l][queries.ch - 'a'];
}

int main(){
   string str = "tutorialspoint";
   int size = str.length();
   int Q = 2;
   countCharFreq(str, size);
   Query queries[Q];
   queries[0].l = 1;
   queries[0].r = 13;
   queries[0].ch = 't';
   queries[1].l = 4;
   queries[1].r = 13;
   queries[1].ch = 'i';
   for(int i = 0; i<Q; i++)
   cout<<"For Query "<<(i+1)<<": The frequency of occurrence of character '"<<queries[i].ch<<"' is "   <<CalcCharFreq( queries[i])<<"\n";
   return 0;
}

ผลลัพธ์

For Query 1: The frequency of occurrence of character 't' is 2
For Query 2: The frequency of occurrence of character 'i' is 2