给定二进制字符串的所有长度为 K 的子串按位或运算后，集合位计数

---

集合位是指数字二进制表示中值为'1'的位。数字的二进制表示只包含两个数字'1'和'0'，也可能以字符串形式出现。给定一个字符串（给定数字的二进制表示）和一个整数 k。我们需要从给定字符串中获取所有长度为 k 的子串，并对它们进行按位或运算，最后返回最终字符串中集合位的数量。

示例

输入

string str = “1100111”
int k = 4

输出

4

解释：我们有四个子串：1100、1001、0011 和 0111，它们的按位或结果是 1111，这意味着这里有四个集合位。

输入

string str = 0110
int k = 4

输出

2

解释：我们只有一个子串，即给定的字符串，因此集合位的数量为 2。

获取所有子串

在这种方法中，我们将遍历字符串，并通过遍历字符串的总长度减去子串的大小来获取所有子串。

我们将通过获取当前子串索引的值来存储最终子串每个索引处的位，如果它是 1，则通过按位或运算，最终结果将为 1。

示例

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

// creating a function to get the required count 
int getCount(string str, int k){
   int len = str.size(); 
   // defining the vector of size k. it will store the number of set bits at any place. Initially there will be zero at each bit 
   vector<int>bits(k,0); 
   // traversing over the string 
   for(int i=0; i<= len-k; i++){
      // getting each substring
      for(int j =0; j<k;j++){
         if(str[i+j] == '1'){
            // if current substring bit is set bit marking it in the vector
            bits[j] = 1;
         }
      }
   }
   // traversing over the created vector to find the result 
   int ans  = 0;
   for(int i=0; i<k; i++){
      if(bits[i] == 1){
         ans++;
      }
   }
   return ans; // returning the final answer
}
int main(){
   string str = "1100111"; // given string 
   int k = 4; // given number 
   cout<<"The count of setbits in the bitwise OR of the given strings substrings of a given length is: "<<getCount(str,k)<<endl;
}

输出

The count of setbits in the bitwise OR of the given strings substrings of a given length is: 4

时间和空间复杂度

上述代码的时间复杂度为 O(N*N)，因为我们使用了嵌套循环来获取每个子串。

上述代码的空间复杂度为 O(N)，因为我们使用了一个数组来存储每个位置的位。

使用差分数组方法

在这种方法中，我们将使用差分数组方法来获取所需答案。首先，我们将创建一个函数来遍历字符串，并在函数中，我们将创建一个数组来存储差分数组结果。

我们将遍历字符串，对于每个索引，我们将获取数据，即当前索引可以在子串中达到哪个最大位置和最小位置，并将该信息标记在差分数组中。

我们将从开头遍历差分数组，并维护一个计数器，统计到目前为止发生的正数的次数。如果当前计数大于零，则将其计为集合位，最后我们将返回数组中集合位的总数。

示例

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

// creating a function to get the required count 
int getCount(string str, int k){
   int len = str.size(); 
   // defining the vector of size k. it will store the starting and ending of number that will make impact. initially there will be zero at each index 
   vector<int>bits(k+1,0); 
   // traversing over the string 
   for(int i=0; i < len; i++){
      if(str[i] == '0'){
         continue; // this bit will not make any impact 
      }
      // getting starting and ending impact of the current index bit 
      int start; 
      start = max(0,k+i-len);
      int end; 
      end = min(i,k-1);
      // updating value int the difference array 
      bits[start]++; 
      bits[end+1]--;
   }
   // traversing over the created vector to find the result 
   int ans  = 0;
   int tot  = 0;
   for(int i=0; i<k; i++){
      tot += bits[i];
      if(tot > 0){
         ans++;
      }
   }
   return ans; // returning the final answer
}
int main(){
   string str = "0110"; // given string 
   int k = 4; // given number 
   cout<<"The count of set bits in the bitwise OR of the given strings substrings of a given length is: "<<getCount(str,k)<<endl;
}

输出

The count of set bits in the bitwise OR of the given strings substrings of a given length is: 2

时间和空间复杂度

上述代码的时间复杂度为 O(N)，因为我们只遍历了字符串一次。此外，我们只遍历了相同大小的数组一次。

上述代码的空间复杂度为 O(N)，因为我们使用了一个数组来存储差分数组结果。

结论

在本教程中，我们实现了一个程序，用于查找给定字符串长度为 k 的子串的按位或运算结果中集合位的数量。我们实现了两个程序，第一个程序是查找所有子串，然后对它们进行按位或运算。第二种方法是使用差分数组，其时间和空间复杂度为 O(N)。