C++で特定の文字Xを1回以上含む部分文字列の個数を求める方法

問題の概要

文字列 str と特定の文字 X が与えられます。求めたいのは、文字 X を少なくとも1回含む部分文字列（substring）の総数です。

たとえば str = "abc"、X = 'a' の場合、条件を満たす部分文字列は「a」「ab」「abc」の3つなので、答えは 3 になります。

入出力例

例1

入力： str = "aabccd"、X = 'c'
出力： 条件を満たす部分文字列の数 ＝ 14

解説： 'c' を1つ以上含む部分文字列は、次の14個です。
"c"、"c"、"bc"、"cc"、"cd"、"abc"、"bcc"、"ccd"、"aabc"、"abcc"、"bccd"、"aabcc"、"abccd"、"aabccd"

例2

入力： str = "settings"、X = 's'
出力： 条件を満たす部分文字列の数 ＝ 15

解説： 's' を1つ以上含む部分文字列は、次の15個です。
"s"、"s"、"se"、"gs"、"set"、"ngs"、"sett"、"ings"、"setti"、"tings"、"settin"、"ttings"、"setting"、"ettings"、"settings"

アルゴリズムの考え方

n 文字の文字列に存在する部分文字列の総数は n×(n+1)/2 ですが、今回はそのうち「X を含むもの」だけを効率よく直接数えます。

基本となるアイデアは次のとおりです。

• 文字列を先頭から走査しながら、直近の X より後ろに続く「X 以外の文字の連続数」を temp として記録します。
• 位置 i で X に出会ったとき、開始位置を i−temp ～ i のいずれかに、終了位置を i ～ 文字列末尾のいずれかに選ぶと、その部分文字列には必ずこの X が含まれます。したがって、この時点で新たに数えられる部分文字列は (temp＋1)×(length－i) 個です。
• どの部分文字列も、その中で最も左側にある X を処理するタイミングでちょうど1回だけカウントされるため、重複カウントは発生しません。
• X を処理したら temp を 0 に戻し、同じ処理を文字列の終端まで繰り返します。

文字列を1度だけ走査すればよいため、計算量は O(n)、必要な追加メモリは O(1) という非常に効率的な手法です。

処理の手順

1. 文字列 str、その長さ length、文字 x を受け取り、条件を満たす部分文字列の個数を返す関数 sub_x() を用意します。
2. カウント用の count と temp をともに 0 で初期化します。
3. for ループで i = 0 ～ length－1 まで走査します。
4. str[i] が x 以外なら、temp を1増やします。
5. str[i] == x なら、count に (temp＋1)×(length－i) を加算し、temp を 0 にリセットします。
6. 走査が完了したら count を結果として返します。

C++ 実装例

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

int sub_x(string str, int length, char x){
    int count = 0;
    int temp = 0;
    for (int i = 0; i < length; i++){
        if (str[i] == x){
            int temp_2 = temp + 1;
            count = count + temp_2 * (length - i);
            temp = 0;
        }
        else{
            temp++;
        }
    }
    return count;
}

int main(){
    string str = "abcabbc";
    int length = str.length();
    char x = 'a';
    cout<<"Count of sub-strings that contain character X at least once are: "<<sub_x(str, length, x);
    return 0;
}

実行結果

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

Count of sub-strings that contain character X at least once are: 19

この例では、文字列 "abcabbc"（7文字）の部分文字列の総数は 7×8÷2 ＝ 28 個です。このうち 'a' を含まないのは、"bc" の範囲に由来する3個と "bbc" の範囲に由来する6個の合わせて9個なので、28－9 ＝ 19 となり、プログラムの出力と一致することが確認できます。

まとめ

「特定の文字を含む部分文字列の個数」を求める問題は、各 X の出現位置に注目し、「使える開始位置の候補数 × 終了位置の候補数」を掛け合わせながら足し込むことで、線形時間 O(n) で解くことができます。部分文字列の数え上げでは、重複を避けるために「どのタイミングで、どの部分文字列をちょうど1回だけ数えるのか」を明確にしておくことが重要なポイントです。