C++で文字列のすべての部分文字列に含まれる母音の出現回数を数える方法

問題概要

英字からなる文字列 str が与えられます。この記事のゴールは、str のすべての部分文字列に登場する母音の総出現回数を求めることです。

たとえば、文字列が「abcde」の場合、部分文字列は「a」「b」「c」「d」「e」「ab」「bc」「cd」「de」「abc」「bcd」「cde」「abcd」「bcde」「abcde」の15個になります。これらの部分文字列に含まれる母音は a と e であり、その出現回数を合計すると 10 になります。

入力例 1

str = "aloe"

出力

Count the number of vowels occurring in all the substrings of given string are:
14

解説： 部分文字列は「a」「l」「o」「e」「al」「lo」「oe」「alo」「loe」「aloe」の10個です。これらに含まれる母音の合計は 14 になります。

入力例 2

str = "http"

出力

Count the number of vowels occurring in all the substrings of given string are:
0

解説： 部分文字列は「h」「t」「t」「p」「ht」「tt」「tp」「htt」「ttp」「http」の10個ですが、いずれにも母音が含まれないため、合計は 0 になります。

アルゴリズムの考え方

すべての部分文字列を実際に生成して母音を数えることも可能ですが、文字列長を n とすると部分文字列の総数は O(n²) 個あり、全体の計算量は O(n³) になってしまいます。そこで本記事では、各文字が何個の部分文字列に含まれるかを事前に計算しておく、より効率的なアプローチを紹介します。

具体的には、i 番目の文字がすべての部分文字列の中で出現する回数をベクトル vec[i] に格納していきます。

• 先頭の文字(0番目)は、長さ n の文字列において必ず n 個の部分文字列に含まれます。
• i 番目の文字については、「i 番目の文字を含む部分文字列の数(n − i)」に「直前の文字までの累計(vec[i − 1])」を加え、「直前の文字のみで構成される部分文字列の数(i)」を引いた値になります。

この漸化式で求まる vec[i] は、実質的に「(i + 1) × (n − i)」、すなわち位置 i の文字を含む部分文字列の総数と一致します。

処理の手順

• 文字列 str を入力として受け取ります。
• 関数 substring_vowels_count(string str, int length) が、文字列とその長さを受け取り、すべての部分文字列に登場する母音の総数を返します。
• カウント用変数 count を 0 で初期化します。
• 整数型のベクトル vec を用意します。
• for ループで i = 0 から i < length まで走査し、i 番目の文字がすべての部分文字列に出現する回数を vec に格納します。
• i = 0 の場合、先頭文字の出現回数は length なので、push_back(length) で vec[0] に設定します。
• それ以外の文字については、temp_1 = length − i、temp_2 = vec[i − 1] − i として、push_back(temp_1 + temp_2) で設定します。
• 続けてもう一度 for ループで str を走査し、str[i] が母音(a、e、i、o、u)であれば vec[i] を count に加算します。
• 最終的に count には、すべての部分文字列における母音の出現総数が格納されます。
• count を結果として返します。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
int substring_vowels_count(string str, int length){
    int count = 0;
    vector<int> vec;
    for (int i = 0; i < length; i++){
        if (i == 0){
            vec.push_back(length);
        } else {
            int temp_1 = length − i;
            int temp_2 = vec[i − 1] − i;
            vec.push_back(temp_1 + temp_2);
        }
    }
    for (int i = 0; i < length; i++){
        if(str[i] == 'a' || str[i] == 'i' || str[i] == 'e' || str[i] == 'o' || str[i] == 'u'){
            count = count + vec[i];
        }
    }
    return count;
}
int main(){
    string str = "honesty";
    int length = str.length();
    cout<<"Count the number of vowels occurring in all the substrings of given string are: "<<substring_vowels_count(str, length);
    return 0;
}

出力結果

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

Count the number of vowels occurring in all the substrings of given string are: 28

まとめ

この手法では、各文字が含まれる部分文字列の個数を漸化式で一度だけ計算するため、時間計算量・空間計算量ともに O(n) で済みます。部分文字列を全列挙して数える素朴な方法(O(n³))と比べ、文字列が長くなっても高速に動作する点が大きなメリットです。