Длина самой длинной цепочки сбалансированных скобок в заданных диапазонах

Во-первых, определите строку «сбалансированных» круглых скобок как строку, такую, что для каждого '(' есть один уникальный, соответствующий ')' где-то после этого '('.

Например, все следующие строки «сбалансированы»:

()

()()

(())()

пока это не:

)(

())(

Учитывая строку скобок (длина ‹= 1 000 000) и список запросов диапазона, найдите максимальную длину сбалансированных скобок в каждом из диапазонов для каждого из ‹ = 100 000 запросов (используя 0-индексацию для диапазонов)

Ex:

()))()(())

Диапазон: [0,3] -> Самый длинный = 2: "()"

Диапазон: [0, 4] -> Самый длинный = 2: "()"

Диапазон: [5, 9] -> Самое длинное = 4: "(())"

Мои мысли таковы:

Во-первых, можно просто определить, является ли строка «сбалансированной», поддерживая стек. Если вы встретите '(', поместите в стек, а когда встретите ')', вытащите его из стека. Если в конце остается '(', то строка не "сбалансирована".

Однако повторение этого для всех диапазонов - это сложность O (N * M), которая слишком велика для размера входных данных.

Теперь, заметив запросы диапазона, на ум приходят суммы префиксов и двоичные индексированные деревья/деревья сегментов. Если вы можете предварительно вычислить весь диапазон сумм префиксов в массив, то вы можете найти меньшие суммы префиксов, взяв разницу, которая будет иметь хорошую сложность big-o.

У меня была идея присвоить значение +1 '(' и значение -1 ')', чтобы каждый раз, когда вы сталкиваетесь с '(', вы добавляли единицу к совокупной сумме, а когда вы сталкиваетесь с ') ' вы уменьшаете. Таким образом, для действительной «сбалансированной» строки, такой как ))(), вы получите: -1 -2 -1 -2.

Однако мой вопрос: как вы используете это, чтобы определить, является ли он «сбалансированным»? Кроме того, поскольку вам нужно найти наибольшую «сбалансированную» строку в заданном интервале, как вы используете возможность проверить, является ли данная подстрока «сбалансированной», чтобы найти эту наибольшую в данном интервале.


string algorithm cumulative-sum parentheses fenwick-tree
person 1110101001    schedule 28.10.2014    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Введение

Для каждой начальной скобки в позиции x вы хотите найти соответствующую закрывающую скобку в позиции y так, чтобы подстрока от x до y, S[x, y], была максимальной сбалансированной подстрокой. Нас не интересуют подстроки, начинающиеся с закрывающей скобки, потому что строки, начинающиеся с них, в лучшем случае так же хороши, как строки, начинающиеся с первой открывающей скобки.

Самое важное наблюдение заключается в следующем: для каждой открывающей скобки, начинающейся с некоторой позиции x' для x < x' < y, соответствующая закрывающая скобка находится в позиции y', где x' < y' < y. Это связано с тем, что каждый префикс S[x, y] содержит как минимум столько же открывающих скобок, сколько закрывающих скобок, поэтому S[x', y] содержит не более столько же открывающих скобок, сколько и закрывающих скобок.

Мы можем использовать это знание для построения дерева, где каждый узел представляет максимально сбалансированную подстроку, поэтому у него есть начальная позиция и конечная позиция. Потомки этого узла представляют сбалансированные подстроки этой подстроки верхнего уровня. Так как могут быть закрывающие скобки, которые не соответствуют открывающей скобке, единого корня нет, поэтому фактически у нас есть лес1.

Картинка говорит больше, чем тысяча слов. Рассмотрим этот пример:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
) ) ( ( ) ( ( ) ) )  )  (  (  )  )

Это даст следующее дерево:

   (2, 9)       (11, 14)
   /     \          |
(3, 4) (5, 8)   (12, 13)
          |
       (6, 7)

Построение дерева

Построить дерево очень просто. Начните с пустого стека. Всякий раз, когда вы встречаете открывающую скобку в позиции x:

  • создать узел (x, ..)
  • добавить этот узел в качестве дочернего узла узла, который в настоящее время находится на вершине стека (если он существует, в противном случае это корень)
  • поместите новый узел в стек

Всякий раз, когда вы встречаете закрывающую скобку в позиции y:

  • извлеките узел (x, ..), который находится на вершине стека (если такого узла нет, это непарная закрывающая скобка: игнорировать)
  • установить закрывающий индекс: (x, y)

Вы сканируете строку один раз и выполняете постоянное количество операций на каждом шаге, поэтому построение структуры выполняется за линейное время.

Запрос дерева

Теперь вам нужно запустить ваши запросы. Учитывая запрос (p, q), вам нужно найти самый большой узел (где размер равен y - x + 1), который полностью содержится в (p, q). Просто выполните два бинарных поиска, чтобы найти начальную и конечную позиции в вашем дереве. (Если символ в позиции p является закрывающей скобкой, вы ищете наименьшую x > p. Точно так же, если символ в позиции q является открывающей скобкой, вы ищете наибольшую y < p.) Найдите наибольший интервал вдоль путей к x и y.

Если ваше дерево хорошо сбалансировано, каждый запрос занимает O(lg n) времени. В худшем случае строка начинается со всех открывающих скобок и заканчивается всеми закрывающими скобками. Тогда запрос может занять линейное время.

1Это можно исправить, добавив перед строкой столько открывающих скобок, сколько несовпадающих закрывающих скобок.

person Vincent van der Weele    schedule 28.10.2014
comment
Есть ли какой-либо метод, который может гарантировать производительность журнала N? Или, иначе, любые оптимизации, которые можно применить к дереву, чтобы получить лучшее среднее значение? Балансировка дерева в этом случае не работает, потому что вам нужно сохранить иерархию, верно? - person 1110101001; 30.10.2014
comment
@user2612743 user2612743 Я думаю, что есть две проблемные ситуации: 1) у узла может быть много дочерних элементов — рассмотрим (()()()...()) и 2) глубина дерева большая — рассмотрим (((...))). Проблема 1 может быть решена путем преобразования k в бинарное дерево с 2k-1 узлами, в основном путем введения некоторых «фиктивных скобок» для дополнительной группировки: ([[()()][()()]][()()]). Однако я пока не вижу простого способа что-то сделать с глубиной дерева. - person Vincent van der Weele; 31.10.2014