C++で無限に繰り返される文字列内の文字の出現回数をカウントする方法

文字列 str、1つの文字、そして正の整数 N が与えられます。文字列 str は無限に繰り返されるものとします。ここでの目的は、繰り返しによって生成される文字列の最初の N 文字の中に、指定した文字が何回出現するかを求めることです。

たとえば、str が「abac」、対象の文字 ch が 'b'、N が 10 である場合を考えてみましょう。

「abacabacabacabac……」の最初の 10 文字の中で、b は 2 回出現します。

注意：str と文字 ch は、大文字・小文字をそろえて扱ってください。

具体例で理解する

例 1

入力：

str = "TPTTTT" ch = 'T' n = 12

出力：

Count of occurrences of a character in a repeated string are: 10

説明：

str 内の 'T' の個数は 5 個、str の長さは 6 です。
n = 12 の場合、str はちょうど 2 回完全に繰り返されるため、
'T' の出現回数は 5 × 2 = 10 となります。

例 2

入力：

str = "sets" ch = 's' n = 15

出力：

Count of occurrences of a character in a repeated string are: 7

説明：

str 内の 's' の個数は 2 個、str の長さは 4 です。
n = 15 の場合、最初の 12 文字で str が 3 回完全に繰り返され、
この部分には 's' が 3 × 2 = 6 回現れます。
残りの 3 文字（set）には 's' が 1 回含まれるため、合計は 6 + 1 = 7 となります。

プログラムで使うアプローチ

このアプローチでは、まず文字列 str 内に文字 ch が何回出現するかを数えます。次に、N を str の長さで割ることで、N 文字の中に str が何回完全に繰り返されるかを求めます（N ÷ str の長さ）。完全な繰り返しの中での ch の出現回数は、単純な掛け算で計算できます。さらに、余りの文字数（N % str の長さ）分については、str の先頭から再度 ch を数え、前の合計に加算します。

• 文字列 str を用意します。
• n を整数、ch を文字、str の長さを整数として受け取ります。
• 関数 occurrences_char(string str, int length, int n, char ch) は、str、ch、n、str の長さを受け取り、繰り返された str の最初の n 文字における ch の出現回数を返します。
• カウント用変数 count を 0 で初期化します。
• for ループを使って str 内の ch の出現回数を数えます。str[i] == ch となるたびに count をインクリメントします。
• n 文字中に str が繰り返される回数は occ = n / length で求まります。
• これらの繰り返しにおける ch の出現回数は count × occ になります。
• 残りの n % length 文字については、str[i] == ch であるかを確認し、該当すれば count をインクリメントします。
• 最後に count を結果として返します。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
int occurrences_char(string str, int length, int n, char ch){
    int count = 0;
    for (int i = 0; i < length; i++){
        if (str[i] == ch){
            count++;
        }
    }
    int occ = n / length;
    count = count * occ;
    for (int i = 0; i < n % length; i++){
        if (str[i] == ch){
            count++;
        }
    }
    return count;
}
int main(){
    string str = "TPTTTT";
    char ch = 'T';
    int n = 12;
    int length = str.size();
    cout<<"Count of occurrences of a character in a repeated string are: "<<occurrences_char(str, length, n, ch);
    return 0;
}

出力結果

上記のコードを実行すると、次の出力が得られます。

Count of occurrences of a character in a repeated string are − 10

まとめ

このアルゴリズムの計算量は O(len)（len は str の長さ）であり、N が非常に大きい場合でも高速に答えを求められる点が大きなメリットです。実際に文字列を N 文字分連結して数えるのではなく、「完全な繰り返し回数 × 1周期あたりの出現回数 ＋ 余りの部分の出現回数」という数学的な考え方を活用することで、時間とメモリの両方を大幅に節約できます。