Truy vấn tần số của các ký tự trong chuỗi con trong C ++

Trong bài toán này, chúng ta được cung cấp một chuỗi. Và mỗi truy vấn Q có hai số nguyên l và r và ký tự ch. nhiệm vụ của chúng ta là tạo một chương trình để giải quyết các truy vấn về tần số của các ký tự trong chuỗi con trong C ++.

Mô tả sự cố :Ở đây với mỗi querry, chúng ta sẽ tìm tần suất xuất hiện của ký tự ‘ch’ trong chuỗi con str [l ... r].

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

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

Đầu ra

2 2

Giải thích

Đối với truy vấn 1 - chuỗi con là "hướng dẫn", ký tự t xuất hiện 2 lần.

Đối với truy vấn 2 - chuỗi con là “ialspoint”, ký tự tôi xuất hiện 2 lần

Cách tiếp cận giải pháp

Cách tiếp cận đơn giản và dễ hiểu để giải quyết vấn đề là duyệt qua chuỗi he từ l đến r cho mỗi quả mọng và đếm sự xuất hiện của haracter ch trong chuỗi.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

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

Đầu ra

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

Một cách tiếp cận khác để giải quyết vấn đề bằng cách sử dụng một mảng được tính toán trước. Ở đây, chúng tôi sẽ tạo một mảng 2D sẽ lưu trữ tần suất của các ký tự cho đến chỉ mục cụ thể, tức là freq [3] [2] sẽ lưu trữ tần suất của ký tự 'c' ở chỉ mục 2. Ban đầu, tất cả các tần số đều bằng 0.

Sau đó, chúng tôi sẽ tính toán trước tần số của ký tự ở mọi giá trị chỉ mục. Sau đó, chúng tôi sẽ tìm tần suất của ký tự trong phạm vi bằng cách lấy tần suất xuất hiện ở chỉ mục l lấy ở chỉ mục r lấy.

Hãy lấy một ví dụ để hiểu vấn đề,

Ví dụ

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

Đầu ra

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