string - 总子串与k个

给定一个二进制字符串s，我们需要找到它的子字符串的数目，其中正好包含k个字符，即“1”。
例如：s=“1010”和k=1，答案=6。
现在，我在累积和数组上使用二进制搜索技术解决了这个问题。
我也用另一种方法来解决它方法如下：
对于每个位置i，找到以i结尾的包含
正好是“1”的k个字符。
要找到以i结尾的子串总数，其中正好包含k个1字符，可以将其表示为索引j的集合，这样子串j到i中正好包含k'1。答案是集合的大小。现在，为了找到给定位置i的所有j，我们可以将问题重新表述为找到所有j
从[1]到[j-1]的个数=从1到i的个总数-[从j到i的个总数=k]。
即从[1]到[j-1]=C[i]-k的个数
等于
C[J-1]=C[I]-K，
其中c是累积和数组，其中
c[i]=从1到i的字符串字符总数。
现在，这个问题很简单，因为，我们可以通过计算所有和C[i]-k的前缀，用这个方程找到j的所有可能值。
但我找到了解决办法，

int main() {
    cin >> k >> S;
    C[0] = 1;
    for (int i = 0; S[i]; ++i) {
        s += S[i] == '1';
        ++C[s];
    }
    for (int i = k; i <= s; ++i) {
        if (k == 0) {
            a += (C[i] - 1) * C[i] / 2;
        } else {
            a += C[i] * C[i - k];
        }
    }
    cout << a << endl;
    return 0;
}

在代码中，S是给定的字符串，K如上所述，C是累积和数组，a是答案。
我不知道代码到底是怎么用乘法运算的。
有人能解释一下算法吗？

最佳答案

如果您看到C[i]的计算方式，C[i]表示ith1和i+1st1之间的字符数。
如果你举个例子S = 1001000

                   C[0] = 1
                   C[1] = 3 // length of 100
                   C[2] = 4 // length of 1000

所以让你怀疑，为什么要乘法
说出你的K=1，然后你想找出只有一个1的子串，现在你知道在第一个1之后有两个0since C[1] = 3。所以子串的数目是3，因为必须包含这个1。

       {1,10,100}

但当你进入第二部分时：C[2] =4
现在如果您看到1000并且您知道您可以生成4个子字符串（它等于c[2]）

     {1,10,100,1000}

你还应该注意到在这之前有C[1]-1个零。
因此，通过包含这些零，您可以生成更多的子字符串，在本例中，通过包含1一次

      0{1,10,100,1000}
      => {01,010,0100,01000}

并且0一次

      00{1,10,100,1000}
      => {001,0010,00100,001000}

所以本质上你是从00开始做C[i]子串，你可以在这个子串之前加上1个零，然后再做另一个i子串。C[i] * C[i-k]-1（-1因为我们想留下最后一个）。

   ((C[i-k]-1)* C[i]) +C[i]
   => C[i-k]*C[i]