C++で部分文字列内の文字出現頻度クエリを効率的に解く方法

この問題では、1つの文字列と Q 個のクエリが与えられます。各クエリは 2 つの整数 l・r と 1 文字 ch で構成されており、部分文字列 str[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 回出現します。

解法1: クエリごとに区間を走査するシンプルな方法

最も直感的なアプローチは、クエリごとに文字列の l から r までを実際に走査し、文字 ch の出現回数を数える方法です。実装は非常に簡単ですが、計算量は O(Q × N) となるため、文字列長 N やクエリ数 Q が大きい場合には非効率になります。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;

struct Query {
    int l, r;
    char ch;
};

// 区間 [l, r] に含まれる文字 ch の出現回数を数える
int calcCharFreq(const string& str, const Query& q) {
    int count = 0;
    for (int i = q.l; i <= q.r; i++) {
        if (str[i] == q.ch)
            count++;
    }
    return count;
}

int main() {
    string str = "tutorialspoint";
    int Q = 2;

    vector<Query> queries = {
        {0, 6, 't'},
        {5, 13, 'i'}
    };

    for (int i = 0; i < Q; i++) {
        cout << "クエリ" << (i + 1) << ": 文字 '" << queries[i].ch
             << "' の出現回数は " << calcCharFreq(str, queries[i]) << " 回です\n";
    }
    return 0;
}

実行結果

クエリ1: 文字 't' の出現回数は 2 回です
クエリ2: 文字 'i' の出現回数は 2 回です

解法2: 累積和による前計算で高速化する方法

より効率的なのが、前計算済みの累積和配列を利用する方法です。freq[i][c] に「文字列の先頭から i 文字分の中に文字 c が出現した回数」を格納する 2 次元配列を用意し、初期値はすべて 0 にしておきます。

前計算が完了していれば、区間 [l, r] における文字 ch の出現回数は「freq[r+1][ch] − freq[l][ch]」という 1 回の減算だけで求められます。前計算に O(N)、各クエリへの回答に O(1) しかかからないため、全体の計算量は O(N + Q) となり、クエリ数が多いケースで大幅な高速化が期待できます。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
// prefixFreq[i][c]: 先頭から i 文字分に文字 c が出現した回数
int prefixFreq[MAXN][26];

void buildPrefixFreq(const string& str) {
    int n = str.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 26; j++)
            prefixFreq[i + 1][j] = prefixFreq[i][j];
        prefixFreq[i + 1][str[i] - 'a']++;
    }
}

// 区間 [l, r] に含まれる文字 ch の出現回数を O(1) で返す
int calcCharFreq(int l, int r, char ch) {
    return prefixFreq[r + 1][ch - 'a'] - prefixFreq[l][ch - 'a'];
}

int main() {
    string str = "tutorialspoint";
    buildPrefixFreq(str);

    cout << "クエリ1: 文字 't' の出現回数は " << calcCharFreq(0, 6, 't') << " 回です\n";
    cout << "クエリ2: 文字 'i' の出現回数は " << calcCharFreq(5, 13, 'i') << " 回です\n";
    return 0;
}

実行結果

クエリ1: 文字 't' の出現回数は 2 回です
クエリ2: 文字 'i' の出現回数は 2 回です

まとめ

クエリ数が少ない場合は素朴な走査でも十分ですが、クエリが多くなると累積和による前計算が圧倒的に有利です。「区間内の特定要素の個数を求める」というタイプの問題では定番のテクニックなので、ぜひマスターしておきましょう。