文字列にC++でサイズKのすべてのバイナリコードが含まれているかどうかを確認します

バイナリ文字列sと整数kがあるとします。長さkのすべてのバイナリコードがsの部分文字列であるかどうかを確認する必要があります。それ以外の場合は、Falseを返します。

したがって、入力がS ="00110110"、k =2の場合、出力はtrueになります。長さ2のバイナリコードは、「00」、「01」、「10」、「11」です。これらはそれぞれインデックス0、1、3、および2に存在します。

これを解決するには、次の手順に従います-

• 1つのセットを定義するv

• temp：=空白の文字列

• req：=2 ^ k

• 初期化i：=0の場合、i

  • temp：=temp + s [i]

  • i> =kの場合、-

    • tempの最初のインデックスから1文字を削除します

  • i> =k-1の場合、-

    • 温度をvに挿入

  • vのサイズがreqと同じ場合、-

    • trueを返す

• falseを返す

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   lli fastPow(lli b, lli p){
      lli ret = 1;
      while (p) {
         if (p & 1) {
            ret *= b;
         }
         b *= b;
         p >>= 1;
      }
      return ret;
   }
   bool hasAllCodes(string s, int k) {
      unordered_set<string> v;
      string temp = "";
      lli req = fastPow(2, k);
      for (lli i = 0; i < s.size(); i++) {
         temp += s[i];
         if (i >= k) {
            temp.erase(0, 1);
         }
         if (i >= k - 1) {
            v.insert(temp);
         }
         if ((lli)v.size() == req)
            return true;
      }
      return false;
   }
};
main(){
   Solution ob;
   cout << (ob.hasAllCodes("00110110",2));
}

入力

"00110110",2

出力

1