C++でバイナリ文字列が長さkのすべての2進パターンを含むか判定する方法

問題の概要

バイナリ文字列と整数 k が与えられたとき、その文字列が k ビットの2進数のすべての順列(パターン)を含んでいるかどうかを判定する問題です。

例として、文字列「11001」で k = 2 の場合を考えてみましょう。2ビットで表せる数値のパターンは「00」「01」「10」「11」の 2² = 4 通りです。この文字列にはこれらすべてのパターンが部分文字列として含まれているため、有効な文字列と判断できます。

アルゴリズムの考え方

長さ k のビット列の組み合わせは合計 2^k 通り存在します。判定は以下の手順で行います。

1. 長さ k のすべての2進パターンを生成し、文字列としてリストに格納する
2. リスト内の各パターンについて、与えられた文字列中に部分文字列として存在するかを順にチェックする
3. すべてのパターンが見つかれば有効(true)、1つでも欠けていれば無効(false)と判定する

パターンの生成では、「000...0」で初期化した k 桁のビット列を、2進数のカウントアップのように最下位桁から繰り上げながら増加させていくことで、すべての組み合わせを漏れなく列挙できます。

C++による実装例

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
vector<string> binaryPermutations(int k){
    vector<string> list;
    int n = 0;
    string bin_str = "";
    for(int i = 0; i<k; i++){
        bin_str += "0";
    }
    int limit = pow(2, k);
    list.push_back(bin_str);
    for(int i=1; i<limit; i++){
        int j = 0;
        while(j <= k){
            if(bin_str[k-1-j] == '0'){
                bin_str[k - 1 - j] = '1';
                break;
            } else {
                bin_str[k - 1 - j] = '0';
                j++;
            }
        }
        list.push_back(bin_str);
    }
    return list;
}
bool hasAllPermutation(string str, int k){
    vector<string> list = binaryPermutations(k);
    for(int i = 0; i<list.size(); i++){
        string substr = list[i];
        std::size_t found = str.find(substr);
        if(found == std::string::npos){
            return false;
        }
    }
    return true;
}
int main() {
    int k = 2;
    string str = "11001";
    if(hasAllPermutation(str, k)){
        cout << "Has All Permutations";
    } else {
        cout << "Not All Permutations are found";
    }
}

コードの解説

binaryPermutations() 関数は、k 桁すべてを 0 に設定した文字列を出発点とし、最下位ビットから上位へ向かって 0→1 の切り替え(繰り上がり)を繰り返すことで、2^k 通りのパターンをすべて生成してリストに格納します。

hasAllPermutation() 関数では、生成済みの各パターンを std::string::find() で検索し、対象文字列中に見つからないパターンが 1 つでもあれば即座に false を返します。すべてのパターンが見つかった場合は true を返します。

実行結果

Has All Permutations

まとめ

文字列長を n とすると、パターンの生成には O(2^k × k)、各パターンの部分文字列検索にも O(n) が必要となるため、全体の計算量は概ね O(2^k × n) となります。k が大きくなるとパターン数が指数関数的に増加する点には注意が必要ですが、k が小さい範囲では非常にシンプルで理解しやすい実装です。