подстроки с k единицами

Question

Учитывая двоичную строку s, нам нужно найти число подстрок, содержащее ровно k символов, которые являются «1».

Например: s = "1010" и к = 1, ответ = 6.

Теперь, я решил его с помощью двоичного поиска техники по кумулятивным массива суммы.

Я также использовал другой подход для его решения. Подход заключается в следующем:

1. Для каждой позиции я, найти общие подстроки, которые заканчиваются на я, содержащий ровно к символы, «1».

2. Чтобы найти полные подстроки, которые заканчиваются в i, содержащие ровно k символов, которые равны 1, его можно представить как множество индексов j, так что подстрока j в i содержит точно k '1. Ответом будет размер набора. Теперь, чтобы найти все такие J для данной позиции я, мы можем перефразировать проблему, как найти все J такое, что

число единиц из [1] до [J - 1] = общее количество единиц от 1 до i - [общее число единиц от j до i = k].

т.е. число единиц от [1] до [J - 1] = С [я] - к

которая равна C [J - 1] = С [я] - к,

где C - совокупный массив сумм, где C [i] = сумма символов строки от 1 до i. Теперь проблема проста, потому что мы можем найти все возможные значения j, используя уравнение, посчитав все префиксы, которые суммируются с C [i] - k.

Но я нашел это решение,

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 является совокупным массивом суммы и есть ответ. Что именно делает код, используя умножение, я не знаю. Может ли кто-нибудь объяснить алгоритм?

Answer 1

Если вы видите путь C[i] рассчитывается, C[i] представляет собой количество символов между i й 1 и i+1 ул 1.

Если взять пример S = 1001000

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

Так подходит к вашему сомнения, Почему умножение

Произнесите K=1, то вы хотите, чтобы выяснить, подстроку, которые имеют только один 1, теперь вы знаете, что после первого 1 есть два нуля since C[1] = 3. Таким образом, количество подстрок будет 3, потому что вы должны включить это 1.

 {1,10,100} 

Но когда вы приходите ко второй части: C[2] =4

теперь, если вы видите 1000 и вы знаете, что вы можете сделать 4 подстроки (которая равна C [2])

 {1,10,100,1000} 

, а также вы должны заметить, что перед этим C[1]-1 нулей 1.

Итак, в том числе и те нули вы можете сделать больше подстроку, в данном случае в том числе 0 раз

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

и 00 раз

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

так по существу вы делаете C[i] подстроки, начиная с 1 и вы можете добавить i количество нулей перед этим и сделать еще одну строку C[i] * C[i-k]-1. i varies from 1 to C[i-k]-1 (-1, потому что мы хотим оставить этот последний).

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