C++の反復法で文字列のすべての部分列（サブシーケンス）を出力する方法

この記事では、C++の反復法（イテレーティブアプローチ）を使って、与えられた文字列からすべての部分列（サブシーケンス）を生成し、出力する方法を解説します。

文字列とは、複数の文字が順番に並んだ配列のことです。

部分列とは

部分列とは、元の文字列からいくつかの文字を削除することで得られる文字列であり、残った文字の並び順は元のまま変更されません。たとえば、文字列「abc」からは「a」「b」「c」「ab」「ac」「bc」「abc」といった部分列を作ることができます。

この種の問題では、「母音で始まり、子音で終わる部分列」を探すという条件が課されることもあります。たとえば次のような入出力が考えられます。

入力：'abc'
出力：ab, ac, abc

「a」は母音、「b」と「c」は子音であるため、条件を満たす部分列は「ab」「ac」「abc」の3つになります。

解き方のアルゴリズム

基本となる考え方は、文字列を走査しながら母音の位置を固定し、その後に続く子音との組み合わせを順に調べていくというものです。手順をまとめると次のようになります。

ステップ1：変数iを使って、文字列の各文字を先頭から順に走査する。
ステップ2：i番目の文字が母音であるかどうかを判定する。
ステップ3：j番目の文字が子音であるかどうかを判定する。
ステップ4：先頭の文字からj番目の文字までをつなげた部分列をHashSetに追加する。
ステップ5：これらの手順を繰り返し、文字列からすべての部分列を見つけ出す。

一方、反復法では「1から2ⁿ−1（nは文字列の長さ）」までのすべての整数を走査します。各整数を2進数で表したとき、ビットが立っている（1になっている）位置の文字を採用すると考えることで、すべての部分列を漏れなく生成できます。

C++による実装例

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

string subString(string s, int binary){
    string sub = "";
    int pos;
    while(binary > 0){
        pos = log2(binary & -binary) + 1;
        sub = s[pos-1] + sub;
        binary = (binary & ~(1 << (pos-1)));
    }
    reverse(sub.begin(), sub.end());
    return sub;
}

void findAllSubStrings(string s){
    map<int, set<string> > sorted_subsequence;
    int len = s.size();
    int limit = pow(2, len);
    for (int i = 1; i <= limit - 1; i++) {
        string sub = subString(s, i);
        sorted_subsequence[sub.length()].insert(sub);
    }
    for (auto it : sorted_subsequence) {
        for (auto ii : it.second)
            cout << ii << " ";
        cout << "\t";
    }
}

int main() {
    string s = "wxyz";
    cout << "The substring are :\n";
    findAllSubStrings(s);
    return 0;
}

実行結果

w x y z wx wy wz xy xz yz wxy wxz wyz xyz wxyz

文字列「wxyz」の場合、長さ1の部分列から長さ4の「wxyz」まで、合計15個（2⁴−1個）の部分列が出力されます。

コードのポイント解説

subString関数：引数binaryを2進数のフラグ列として解釈し、ビットが1になっている位置に対応する文字を取り出して部分列を組み立てます。「binary & -binary」で最下位のセットビットのみを抽出し、log2でその位置を特定した後、該当ビットをクリアしながら処理を繰り返します。

findAllSubStrings関数：1から2ⁿ−1までの各整数に対してsubString関数を呼び出し、生成された部分列をmap<int, set<string>>に格納します。キーを部分列の長さ、値をsetにすることで、自動的なソートと重複の排除が同時に実現されます。

この手法の計算量はO(2ⁿ×n)となり、文字列が長くなるほど指数関数的に増加します。そのため、比較的短い文字列（目安としてn≤20程度まで）に適したアプローチです。