C++で配列内のプレフィックス（接頭辞）の最大出現回数を求める方法

この問題では、すべて小文字から構成される文字配列が与えられます。私たちのタスクは、配列内で最も多く出現するプレフィックス（接頭辞）を見つけることです。

具体的には、出現回数が最大となる空でないプレフィックスについて、その出現回数を数える必要があります。

問題を理解するための例

入力 : string = "xyyzkxyyzk"
出力 : 2

解法のアプローチ

この問題の鍵となるのは、次のシンプルな発想です。配列のプレフィックスは必ず文字列の最初の文字を含みます。繰り返し出現するプレフィックスも同様に、必ず先頭の文字を持っています。

また、文字列の最初の文字そのものは、文字数が1だけの最短のプレフィックスです。したがって、最も多く出現するプレフィックスは必ず文字列の最初の文字になることが保証されます。

この考察により、問題は「文字列の中に最初の文字が何回出現するかを数える」という非常にシンプルな問題へと帰着します。

アルゴリズム

• 小文字アルファベットからなる文字列を読み込みます。
• 必要なプレフィックスの出現回数を返す関数を作成します。
• カウント用変数 count を 0 で初期化します。
• 文字列全体を走査し、最初の文字の出現頻度を数えます。
• 最初の文字の出現頻度を出力します。これが文字列のプレフィックスの最大出現回数となります。

実装例

以下は、上記の解法の動作を示すC++プログラムです。

#include <iostream>
using namespace std;

int findPrefixOccurence(string str){
    char chars = str[0];
    int countOccrence = 0;
    for (int i = 0; i < str.length(); i++) {
        if (str[i] == chars)
            countOccrence++;
    }
    return countOccrence;
}

int main(){
    string str = "xyyzxxyyzxyxx";
    cout<<"The maximum occurence of prefix in the array is "<<findPrefixOccurence(str);
    return 0;
}

出力結果

The maximum occurence of prefix in the array is 6

計算量について

このアルゴリズムは文字列を一度だけ走査するため、時間計算量は O(n)、追加のメモリ使用量は O(1) となります。文字列の長さに関わらず効率的に動作するのが特徴です。