การสืบค้นความถี่ของตัวอักษรใน Substring ใน C++

ในปัญหานี้ เราได้รับสตริง (string) และ Q queries แต่ละ query มีจำนวนเต็ม 2 ค่า l และ r และตัวอักษร ch ภารกิจคือการสร้างโปรแกรมเพื่อแก้ปัญหาการสืบค้นความถี่ของตัวอักษรใน substring ใน C++

คำอธิบายปัญหา

สำหรับแต่ละ query เราจะหาความถี่ของการปรากฏของตัวอักษร 'ch' ใน substring str[l...r]

ตัวอย่างเพื่อเข้าใจปัญหา

อินพุต

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

เอาต์พุต

2 2

คำอธิบาย

Query 1 − substring คือ "tutoria" ตัวอักษร t ปรากฏ 2 ครั้ง

Query 2 − substring คือ "ialspoint" ตัวอักษร i ปรากฏ 2 ครั้ง

แนวทางแก้ปัญหา

วิธีที่ง่ายและตรงไปตรงมาคือการวนลูปผ่านสตริงจาก l ถึง r สำหรับแต่ละ query และนับจำนวนครั้งที่ตัวอักษร 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

วิธีอีกวิธีหนึ่ง คือการใช้อาร์เรย์ที่คำนวณล่วงหน้า (pre-computed array) เราจะสร้างอาร์เรย์ 2 มิติที่จะเก็บความถี่ของตัวอักษรจนถึงดัชนีที่กำหนด เช่น freq[3][2] จะเก็บความถี่ของตัวอักษร 'c' ที่ดัชนี 2 เริ่มต้นความถี่ทั้งหมดเป็น 0

จากนั้นเราจะคำนวณล่วงหน้าความถี่ของตัวอักษรที่ทุกดัชนี หลังจากนั้น หาความถี่ในช่วงโดยการลบความถี่ที่ดัชนี l ออกจากความถี่ที่ดัชนี r

ตัวอย่างโปรแกรม (วิธี Pre-computed Array)

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

เอาต์พุต

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