【C++】バイナリ文字列に1〜Nの2進表現がすべて部分文字列として含まれるか判定する方法

問題概要

バイナリ文字列 S と正の整数 N が与えられたとします。1 から N までのすべての整数 X について、その 2 進表現が文字列 S の部分文字列として含まれる場合に限り true を返すのが目的です。

例えば、S = "0110"、N = 3 のケースを考えてみましょう。1 の 2 進表現は "1"、2 は "10"、3 は "11" であり、これらはいずれも "0110" の中に含まれています。したがって、この場合は true が返ります。

解法のアプローチ

この問題は、次の手順で解くことができます。

• 整数 n を受け取り、その 2 進表現を文字列として返す convert() メソッドを定義します。
• 結果を格納する ret を空文字列で初期化します。
• n が 0 になるまで、次の処理を繰り返します。
  • ret に n を 2 で割った余り（n mod 2）を連結します。
  • n を 2 で割ります（n := n / 2）。
• ループ終了後、ret を反転して返します。これで正しい桁順の 2 進表現の文字列が得られます。
• メインの判定処理では、i を N から N/2 まで 1 ずつ減らしながら、以下を繰り返します。
  • temp := convert(i) として、i の 2 進表現を求めます。
  • temp が S 内に見つからない場合は false を返します。
• すべてのチェックを通過できれば、true を返します。

なぜ N から N/2 の範囲だけ調べればよいのか

実は、1 から N/2 までの任意の整数 x の 2 進表現は、N/2 以上 N 以下のある整数 y の 2 進表現の先頭部分（接頭辞）と必ず一致します。bin(y) が S に含まれるなら、その出現位置の先頭にあたる bin(x) も自動的に S に含まれるためです。つまり、範囲 [N/2, N] だけを確認すれば十分で、チェック対象を約半分に削減できます。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   string convert(int n){
      string ret = "";
      while(n){
         ret += (n % 2) + '0';
         n /= 2;
      }
      reverse(ret.begin(), ret.end());
      return ret;
   }
   bool queryString(string S, int N) {
      for(int i = N; i >= N/2; i-- ){
         string temp = convert(i);
         if(S.find(temp) == string::npos) return false;
      }
      return true;
   }
};
main(){
   Solution ob;
   cout << (ob.queryString("0110", 3));
}

入力

"0110"
3

出力

1

出力が 1（true）になっています。これは、1・10・11 のすべての 2 進表現が "0110" に含まれていることを示しています。

なお、convert() メソッドでは下位ビットから順に文字を連結しているため、最後に reverse() で反転して正しい桁順に整えています。また、各判定では string::find() を使って部分文字列の有無を確認しており、見つからない場合は即座に false を返すことで無駄な計算を避けています。