C++에서 부분 문자열의 문자 빈도 쿼리

이 문제에서는 문자열이 제공됩니다. 그리고 Q 쿼리에는 각각 두 개의 정수 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로 순회하고 문자열에서 문자 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

또 다른 접근 방식 문제를 해결하는 방법은 미리 계산된 배열을 사용하는 것입니다. 여기에서 특정 인덱스까지의 문자 빈도를 저장할 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