それはすべて、次のCodeforces Roundのサイトcodeforces.ruで、面白いパズル「ブラケットシーケンス」を見て、「面白くない」方法で解決したくなかったという事実から始まりました。
簡単に言えば、問題の条件は、文字「（」、「）」、「[」、および「]」のみで構成される行で、「[」と同じ数のブラケットを含む正しいステープルシーケンスを見つけることに限定されます。
まず、フラットラインをより便利な階層表現に変換します。
with brackets as (select '[[)]([][][][[()[()[()()]]]])]' b from dual) select substr(b,level,1) q, level curr_pos, level - 1 prev_pos from brackets connect by substr(b,level,1) is not null
各行には、別のブラケット、現在のブラケットの位置、前のブラケットの位置があります。 これで、あなたはすでに何かをすることができます。
すべての正しいブラケットシーケンスを見つけることは残っています。 ここから楽しみが始まります。
式の正確さを判断するために、ブラケットを格納できるスタックがないため、「トリック」に進む必要がありました。
「（」または「[」で始まるすべての可能なシーケンスを検索します（残りはデフォルトでは間違っています）。このようなシーケンスごとに、最初と最後の括弧の位置と最後の括弧の「入れ子レベル」を決定します。
「（」「1-レベル」
「（」「第2-レベル」
.. ... .. ..
「]」「第2-レベル」
.. ... .. ...
- 次の場合、レベルが増加します。ブラケットが開き、その前に何もないか、開口部があった。
- ブラケットが開いていて、閉じる前、またはブラケットが閉じていて、開く前のレベルは変わりません。
- ブラケットが閉じると、閉じる前にレベルが低下します。
with brackets as (select '[[)]([][][][[()[()[()()]]]])]' b from dual) , all_brackets as (select substr(b,level,1) q, level curr_pos, level-1 prev_pos from brackets connect by substr(b,level,1) is not null) select replace(sys_connect_by_path(q,'-'), '-') str, q, connect_by_root(curr_pos) start_pos, curr_pos end_pos, sum( case when (q = '(' or q = '[') and (prior q is null) then 1 when (q = '(' or q = '[') and (prior q = '(' or prior q = '[') then 1 when (q = '(' or q = '[') and (prior q = ']' or prior q = ')') then 0 when (q = ')' or q = ']') and (prior q = '(' or prior q = '[') then 0 when (q = ')' or q = ']') and (prior q = ')' or prior q = ']') then -1 end) over (partition by connect_by_root(curr_pos) order by connect_by_root(curr_pos), curr_pos) bracket_level from all_brackets connect by prior curr_pos = prev_pos start with q = '(' or q = '['
このデータを使用して、正しいシーケンスを乱す「害虫」ブラケットを決定できます。 これを行うには、取得したすべてのシーケンスを調べ、次の括弧が「現れる」ときに、現在の括弧と同じレベルにある前の括弧を見つけます（分析関数の遅延についてOracleに感謝します）。 いずれかのレベルで次のいずれかの状況が発生すると、誤ったシーケンスが取得されます。
- 閉じ括弧が閉じます
- 括弧は正方形を閉じます
- 角かっこは丸く閉じます
この反復の開始括弧は、シーケンスを「ブレーク」できません。
with brackets as (select '[[)]([][][][[()[()[()()]]]])]' b from dual) , all_brackets as (select substr(b,level,1) q, level curr_pos, level - 1 prev_pos from brackets connect by substr(b,level,1) is not null), brackets_comb as (select replace(sys_connect_by_path(q,'-'), '-') str, q, connect_by_root(curr_pos) start_pos, curr_pos end_pos, sum( case when (q = '(' or q = '[') and (prior q is null) then 1 when (q = '(' or q = '[') and (prior q = '(' or prior q = '[') then 1 when (q = '(' or q = '[') and (prior q = ']' or prior q = ')') then 0 when (q = ')' or q = ']') and (prior q = '(' or prior q = '[') then 0 when (q = ')' or q = ']') and (prior q = ')' or prior q = ']') then -1 end) over (partition by connect_by_root(curr_pos) order by connect_by_root(curr_pos), curr_pos) bracket_level from all_brackets connect by prior curr_pos = prev_pos start with q = '(' or q = '[') select start_pos, end_pos, str, case when q = ')' and lag(q) over (partition by start_pos, bracket_level order by start_pos, bracket_level, end_pos) = '(' then 'ok' when q = '(' and lag(q) over (partition by start_pos, bracket_level order by start_pos, bracket_level, end_pos) = ')' then 'ok' when q = '(' and lag(q) over (partition by start_pos, bracket_level order by start_pos, bracket_level, end_pos) = ']' then 'ok' when q = ']' and lag(q) over (partition by start_pos, bracket_level order by start_pos, bracket_level, end_pos) = '[' then 'ok' when q = '[' and lag(q) over (partition by start_pos, bracket_level order by start_pos, bracket_level, end_pos) = ']' then 'ok' when q = '[' and lag(q) over (partition by start_pos, bracket_level order by start_pos, bracket_level, end_pos) = ')' then 'ok' when lag(q) over (partition by start_pos, bracket_level order by start_pos, bracket_level, end_pos) is null and bracket_level > 0 then 'ok' else 'not ok!' end status from brackets_comb bc
したがって、同じ位置（start_pos）から始まり、括弧の数で順序付けられたシーケンスの各セットに対して、最初の誤ったシーケンスが見つかりました。
そのようなシーケンスの各セットで、「間違った」シーケンスの後にシーケンスを「スロー」し、残りのすべてについて、開いたブラケットが閉じていることを確認します（このため、各種類の開いたブラケットと閉じたブラケットの数を数えるだけで十分です）。
その結果、最大数の「[」を持つブラケットシーケンスである、おそらく唯一ではない彼女 （いいえ、あなたの夢の女の子ではない）を見つけることが残っています。
すべてのリクエスト：
with brackets as (select '[[]])[([[]][[(]])]' b from dual) , all_brackets as (select substr(b,level,1) q, level curr_pos, level - 1 prev_pos from brackets connect by substr(b,level,1) is not null), brackets_comb as (select replace(sys_connect_by_path(q,'-'), '-') str, q, connect_by_root(curr_pos) start_pos, curr_pos end_pos, sum( case when (q = '(' or q = '[') and (prior q is null) then 1 when (q = '(' or q = '[') and (prior q = '(' or prior q = '[') then 1 when (q = '(' or q = '[') and (prior q = ']' or prior q = ')') then 0 when (q = ')' or q = ']') and (prior q = '(' or prior q = '[') then 0 when (q = ')' or q = ']') and (prior q = ')' or prior q = ']') then -1 end) over (partition by connect_by_root(curr_pos) order by connect_by_root(curr_pos), curr_pos) bracket_level from all_brackets connect by prior curr_pos = prev_pos start with q = '(' or q = '['), brackets_comb_status as (select start_pos, end_pos, str, case when q = ')' and lag(q) over (partition by start_pos, bracket_level order by start_pos, bracket_level, end_pos) = '(' then 'ok' when q = '(' and lag(q) over (partition by start_pos, bracket_level order by start_pos, bracket_level, end_pos) = ')' then 'ok' when q = '(' and lag(q) over (partition by start_pos, bracket_level order by start_pos, bracket_level, end_pos ) = ']' then 'ok' when q = ']' and lag(q) over (partition by start_pos, bracket_level order by start_pos, bracket_level, end_pos) = '[' then 'ok' when q = '[' and lag(q) over (partition by start_pos, bracket_level order by start_pos, bracket_level, end_pos) = ']' then 'ok' when q = '[' and lag(q) over (partition by start_pos, bracket_level order by start_pos, bracket_level, end_pos) = ')' then 'ok' when lag(q) over (partition by start_pos, bracket_level order by start_pos, bracket_level, end_pos) is null and bracket_level > 0 then 'ok' else 'not ok!' end status from brackets_comb bc) select str "", cnt " [", start_pos " ", end_pos " " from ( select str, start_pos, end_pos, length(regexp_replace(str,'[\)\(]',''))/2 cnt, max(length(regexp_replace(str,'[\)\(]',''))/2) over (order by null) best_cnt from ( select str, start_pos, end_pos, nvl( lag( case when status = 'ok' then null else status end ignore nulls) over (partition by start_pos order by start_pos, end_pos), status ) status from brackets_comb_status ) where status = 'ok' and length(replace(str,'[','')) = length(replace(str,']','')) and length(replace(str,'(','')) = length(replace(str,')','')) ) result where best_cnt = cnt