C++の部分文字列の文字の頻度に関するクエリ

この問題では、文字列が与えられます。また、Qクエリにはそれぞれ2つの整数lとrおよび文字chがあります。私たちのタスクは、C++のサブストリング内の文字の頻度に関するクエリを解決するプログラムを作成することです。

問題の説明 ：ここでは、各クエリについて、部分文字列str [l...r]に文字「ch」が出現する頻度を確認します。

問題を理解するために例を見てみましょう

入力

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

出力

2 2

説明

クエリ1の場合 −部分文字列は「tutoria」で、文字tは2回出現します。

クエリ2の場合 −部分文字列は「ialspoint」で、文字iは2回出現します

ソリューションアプローチ

問題を解決するための簡単で直接的なアプローチは、各クエリの文字列をlからrにトラバースし、文字列内のharacterchの発生をカウントすることです。

ソリューションの動作を説明するプログラム

例

#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

別のアプローチ 問題を解決するには、事前に計算された配列を使用します。ここでは、特定のインデックスまでの文字の頻度を格納する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 = "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