C ++中子字符串中字符频率的查询

在这个问题上，我们得到一个字符串。Q查询每个都有两个整数l和r以及字符ch。我们的任务是创建一个程序来解决C ++中子字符串中字符频率的查询。

问题描述：在这里，对于每个查询，我们将在子字符串str [l ... r]中找到字符“ ch”的出现频率。

让我们举个例子来了解这个问题，

输入值

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

输出结果

2 2

说明

对于查询1-子字符串为“ tutoria”，字符t出现2次。

对于查询2-子字符串为“ ialspoint”，字符i出现2次

解决方法

解决该问题的简便方法是将每个Querry的弦从l遍历到r，并计算弦中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 = "nhooo";
   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

解决问题的另一种方法是使用预先计算的数组。在这里，我们将创建一个2D数组，该数组将存储直到特定索引的字符频率，即freq [3] [2]将在索引2处存储字符'c'的频率。最初，所有频率均为0。

然后，我们将预先计算每个索引值处字符的频率。之后，我们通过从索引r处减去索引l处的出现频率，来找到该字符的频率。

让我们举个例子来了解这个问题，

示例

#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 = "nhooo";
   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