対応のとれた括弧列

「正規括弧列」「正しい括弧列」「平衡括弧列」「バランスの取れた括弧列」などと呼ばれることもある。

形式的な定義

ここで、文字列$ s, tに対して、$ s + tを「$ sおよび$ tをこの順番で連結したもの」とする。

$ S_0 = \{""$ \}

すべての非負整数$ iに対して、$ S_{i + 1} = \{"("$ + s +")"$ , s + t | s, t \in S_i\}

ある文字列$ sが正規括弧列であるとは、ある整数$ iが存在し、$ s \in S_iであることと同値。

定義が壊れがち

判定

どの部分においても、そこまでに現れた(の数が)の数以上かつ、最後は同じになる

セグ木にのせる

対応が必ずしも取れていない括弧列をセグ木にのせる

気持ち: 対応の取れている部分をすべて消していくと、))…)(…((が残るので、閉じ括弧と開き括弧を数える

単位元: $ (0, 0)

値: ( → $ (0, 1), ) → $ (1, 0)

演算: $ (a, b) * (c, d) = (a + \max\{0, c - b\}, \max\{0, b - c\} + d)

区間演算の結果が$ (0, 0)なら対応がとれている

また、結果が$ (d, u)のとき、$ \left\lceil\frac{d}{2}\right\rceil + \left\lfloor\frac{d \bmod 2 + u}{2}\right\rfloor文字変えると対応がとれるようになる

数え上げ

$ 2n文字の対応が取れた括弧列の個数はカタラン数$ C_nに等しい

$ C_n = \frac{1}{n + 1} \binom{2n}{n}

$ C_0 = 1

$ C_{n+1} = \sum_{k=0}^n C_k C_{n - k}

一意に生成

$ S_0 = \{\varepsilon\}

$ S_{n + 1} = \{ (s)t | k \le n \wedge s \in S_k \wedge t \in S_{n - k} \}

参考