Truy vấn tần suất ký tự trong xâu con trong C++

Trong bài toán này, ta được cho một xâu. Và Q truy vấn, mỗi truy vấn có hai số nguyên l và r và ký tự ch. Nhiệm vụ là tạo chương trình giải quyết truy vấn: tần suất ký tự trong xâu con trong C++.

Mô tả bài toán

Với mỗi truy vấn, ta tìm tần suất xuất hiện của ký tự 'ch' trong xâu con str[l...r].

Ví dụ minh họa

Đầu vào

str = "tutorialspoint"
Q = 2
0 6 t
5 13 i

Đầu ra

2 2

Giải thích

Truy vấn 1 – xâu con là "tutoria", ký tự 't' xuất hiện 2 lần.

Truy vấn 2 – xâu con là "ialspoint", ký tự 'i' xuất hiện 2 lần.

Phương pháp giải

Cách trực tiếp: duyệt xâu từ l đến r cho mỗi truy vấn và đếm số lần xuất hiện của ký tự ch.

Chương trình minh họa:

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

Cách tiếp cận khác là dùng mảng tiền tính. Tạo mảng 2D lưu tần suất ký tự đến chỉ số i. Tức freq[3][2] lưu tần suất ký tự 'c' tại chỉ số 2. Ban đầu tất cả tần suất = 0.

Sau đó tiền tính tần suất tại mỗi chỉ số. Khi truy vấn, tần suất trong khoảng = freq[r][ch] - freq[l-1][ch] (cần xử lý biê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(charFreq));
    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