C++で文字Xで始まり文字Yで終わる部分文字列の個数を数える方法

文字列 str が与えられたとき、「先頭の文字が X と一致し、末尾の文字が Y と一致する」部分文字列がいくつあるかを数えるのが本記事の目的です。たとえば、入力が "artact"、X='a'、Y='t' の場合、条件を満たす部分文字列は "art"、"act"、"artact" の 3 つとなるため、答えは 3 になります。

具体例で理解する

例 1

入力 − str="abcccdef"、X='a'、Y='c'

出力 − 条件を満たす部分文字列の数: 3

説明 − 該当する部分文字列は次のとおりです。

"abc"、"abcc"、"abccc"。合計 3 個。

例 2

入力 − str="tempest"、X='t'、Y='t'

出力 − 条件を満たす部分文字列の数: 3

説明 − 該当する部分文字列は次のとおりです。

"t"(先頭)、"tempest"、"t"(末尾)。合計 3 個。

X と Y が同じ文字の場合でも、先頭の "t" と末尾の "t" はそれぞれ独立した部分文字列としてカウントされる点に注意してください。

アルゴリズムの考え方

文字列を先頭から順に走査し、文字 X を見つけるたびにその出現回数を記録します。そして文字 Y に出会ったタイミングで、それまでに数えた X の個数を答えに加算します。この方法なら、すべての部分文字列を実際に生成することなく、線形時間 O(n) で答えを求められます。

• 文字列 str を受け取り、長さを str.size() で取得します。
• 関数 X_Y(string str, int length, char X, char Y) は、文字列 str と文字 X・Y を引数に取り、X で始まり Y で終わる部分文字列の個数を返します。
• 結果を格納する変数 count を 0 で初期化します。
• x_total は、これまでに走査した範囲に含まれる文字 X の個数を表します(初期値 0)。
• for ループで i=0 から i<length まで文字列を走査します。
• str[i]==X のとき、x_total をインクリメントして X の出現数を更新します。
• str[i]==Y のとき、count に x_total を加算します。まだ X が現れていなければ x_total は 0 なので加算しても影響はなく、X が存在していれば、現在の Y は「その X から始まる部分文字列」の末尾文字となります。
• 最後に count を結果として返します。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
int X_Y(string str, int length, char X, char Y){
    int count = 0;
    int x_total = 0;
    for (int i = 0; i < length; i++){
        if(str[i] == X){
            x_total++;
        }
        if (str[i] == Y){
            count = count + x_total;
        }
    }
    return count;
}
int main(){
    string str = "defaabbcchhkl";
    int length = str.size();
    char X = 'd';
    char Y = 'a';
    cout<<"Count of substrings that starts with character X and ends with character Y are: "<<X_Y(str, length, X, Y);
    return 0;
}

実行結果

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

Count of substrings that starts with character X and ends with character Y are: 2

この例では、"d" で始まり "a" で終わる部分文字列は "defa" と "defaa" の 2 つであるため、正しく 2 が出力されます。文字列を一度だけ走査すればよいため、計算量は O(n) と非常に効率的です。