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

Question

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

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

()

()()

(())()

в то время как они не являются:

) (

()) (

Дана строка скобок (длина < = 1000000), а также список запросов диапазона, найти максимальную длину сбалансированные скобки внутри каждый из диапазонов для каждого из < = 100000 запросов (с использованием 0-индексации для диапазонов)

Ex:

()))() (())

Диапазон: [0,3] -> Серия = 2: "()"

Диапазон: [0, 4] -> Серия 2 = : "()"

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

Мои мысли следующим образом:

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

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

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

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

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

Answer 1

Введение

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

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

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

В картине написано более тысячи слов. Рассмотрим следующий пример:

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) раз. В худшем случае строка начинается со всех открывающих кронштейнов и заканчивается всеми закрывающими скобами. Тогда запрос может занять до линейного времени.

_{Мы могли бы исправить это, добавив столько открывающей скобки в начале строки, поскольку есть непарные закрывающие скобки.}