Как найти число 010 в определенном диапазоне двоичной строки

Question

Дана двоичная строка. Как найти вхождения "010" в определенном диапазоне строки.
Например, у меня есть строка "0100110". Если заданный диапазон равен 3 7 (индексирование на основе 1), выходной сигнал будет равен 4. Я не мог найти более быстрый способ решить это.

Пытаясь это, я могу решить это в O(N) сложности. Подход заключается в том, чтобы - сначала я укажу положение всех "1" в определенном диапазоне, и, используя эту позицию, я выясню число "0" как вперед, так и вперед. А затем умножьте число "0", найденное в спине, на один "1" с числом "0" в найденном в четверти. Затем суммируйте умноженный результат для каждого из '1' в пределах определенного диапазона.

Для данного примера позиция '1' в пределах диапазона составляет {5, 6}. Теперь для индекса 5 у меня число "0" в обоих направлениях равно 2 и 1 соответственно. Таким образом, мы можем сделать подпоследовательность "010" равной 2. Аналогично для индекса 6 мы также получаем ответ 2. Всего мы можем сделать подпоследовательность "010" всего 4 раза.

Но когда у нас есть несколько Q запросов определенных диапазонов для данной строки, мой подход легко достигает временной сложности O (N²). Я много пробовал, но не смог найти способ его оптимизировать. Кто-нибудь может мне помочь с подходом, который меньше, чем сложность O (N²)? Просто упомянуть, что ограничение по времени должно быть 1 секунда. Это будет плюсом, если вы предоставите псевдокод.

~ Заранее спасибо.

Answer 1

Предварительная обработка: сделать вспомогательный массив, содержащий кумулятивное число нулей до заданной позиции (с aux[0]=0)

  0 1 0 0 1 1 0  //string
0 1 1 2 3 3 3 4  //aux array A[]

Для данного L..R сканирование диапазона для них, для каждого индекса k 1 получить число нулей в диапазоне - O(1) операция

P[k] = (A[k] - A[L-1]) * (A[R] - A[k])
S = Sum(P[k], k=L..R)

Итак, мы имеем O(R-L) время на запрос и худший случай O(Q*N) для Q запросов

Но посмотрите на формулу полностью:

P[k] = (A[k] - A[L-1]) * (A[R] - A[k]) = 
       A[k] * (A[R] + A[L-1]) - A[k]^2 - A[R] * A[L-1] = 
       A[k] * LRSum - A[k]^2 - LRProd
S = Sum(A[k] for ones) * LRSum - Sum(A[k]^2) - LRProd * NumOfOnes 

Обратите внимание, что LRSum а также LRProd являются константами для данного запроса, и мы должны вычислить суммы A[k] для позиций единиц и сумму квадратов для тех же позиций. Кажется, мы можем использовать ту же идею кумулятивного массива и получить результат в O(1) за запрос.

Быстрая проверка дает (3+3)*5 - (9+9) - 4*2 = 30-18-8 = 4 для вашего примера.

Использование накопительных массивов:

  0 1 0 0 1  1  0  //string
0 1 1 2 3 3  3  4  //aux array A[]
0 0 1 1 1 4  7  7  //aux array B[]
0 0 1 1 1 10 19 19  //aux array C[]

Result = (B[R] - B[L-1]) * (A[R] + A[L-1]) - (C[R] - C[L-1]) - 
                 A[R] * A[L-1] * (R - L - 1 - (A[R] - A[L-1])) = 
         (7-1) * (4 + 1) - (19 - 1) - 4 * 1 * (7 - 2  - 4 + 1) = 4