C++で文字列内の特定パターンに一致する長さ3の部分列の個数を数える方法

この記事では、文字列 str と長さ3の部分文字列 sub_str が与えられたとき、str の中に sub_str と同じ文字順で現れる部分列（サブシーケンス）が何個あるかを求める方法を解説します。

例えば、「act」というパターンは「cataract」という文字列の中に3回部分列として出現します。

具体的な例で確認してみましょう。

入力例と出力例

入力 − str = "settlement"、sub_str = "set"

出力 − 与えられた文字列における長さ3の部分列の個数：5

説明 − 条件を満たす部分列は以下の通りです。

1. set tlement,
2. se t t lement,
3. se ttlemen t,
4. s ettl e men t,
5. settlem e n t

入力 − str = "knowledge"、sub_str = "now"

出力 − 与えられた文字列における長さ3の部分列の個数：1

説明 − 条件を満たす部分列は「know ledge」の1つだけです。

プログラムで使用するアプローチ

ここでは、forループを使って文字列 str を先頭から順に走査していきます。str[i] が sub_str[0]（1文字目）と一致したら、続く位置（i+1 以降）に sub_str[1]（2文字目）と一致する文字があるかを調べます。さらにそこで一致が見つかれば、その次の位置（j+1 以降）に sub_str[2]（3文字目）と一致する文字があるかを確認し、すべて揃った時点でカウントを1増やします。

アルゴリズムの手順

• 文字列 str と部分文字列 sub_str を受け取ります。
• 関数 subset_occurrence(string str, int length, string sub_str) が文字列を受け取り、str 内に存在する sub_str と一致する部分列の個数を返します。
• forループで i=0 から i<length まで str を走査します。
• str[i]==sub_str[0] なら1文字目が見つかったので、j=i+1 から j<length の範囲で次の文字を探します。
• str[j]==sub_str[1] なら2文字目が一致したので、k=j+1 から k<length の範囲で3文字目を探します。
• str[k]==sub_str[2] なら3文字もすべて一致したため、count をインクリメントします。
• 最後に count を結果として返します。

実装例

#include<iostream>
using namespace std;
int subset_occurrence(string str, int length, string sub_str){
    int count = 0;
    for (int i=0; i<length; i++){
        if (str[i]==sub_str[0]){
            for (int j=i+1; j< length; j++){
                if(str[j]==sub_str[1]){
                    for(int k=j+1; k<length; k++){
                        if(str[k]==sub_str[2])
                            { count++; }
                    }
                }
            }
        }
    }
    return count;
}
int main(){
    string str = "TUTpoinTUTpoinTUT";
    int length = str.length();
    string sub_str = "TUT";
    cout<<"与えられた文字列における長さ3の部分列の個数: "<<subset_occurrence(str, length, sub_str);
    return 0;
}

実行結果

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

与えられた文字列における長さ3の部分列の個数: 19

まとめ

この方法では三重のネストされたループを使用するため、計算量は O(n³) となります。文字列が短い場合には十分実用的ですが、より長い文字列に対しては、各文字の出現位置を前処理で記録するなどして効率化することも可能です。ただし、本稿で紹介したシンプルな三重ループのアプローチは、ロジックが直感的で理解しやすく、部分列の数え方の基本を学ぶのに最適な例といえます。