括号问题

Published: by Creative Commons Licence

  • Tags:

括号数目统计

要计算长度为$n$的有效括号对数目,可以通过卡特兰数来计算。

数量为:

\[{2n\choose n} - {2n \choose n + 1}\]

交错括号问题

给定两类括号$()$和$[]$。一个合法的括号序列$s$有如下几种:

  • $s$是空串
  • $s=(a)$,其中$a$是合法括号序列
  • $s=[a]$,其中$a$是合法括号序列
  • $s=ab$,其中$a$和$b$都是合法括号序列

题目1:长度为$n$的01字符串有多少,满足将0替换为圆括号,将1替换为方括号,有机会得到一个合法的括号序列。

首先$n$如果是奇数,那么结果一定是$0$,接下来我们假定$n$是偶数。

考虑由$0$占领的下标,记录$a$为其中奇数的数目,$b$为其中偶数的数目。可以发现如果$a\neq b$,则必定会出现相同奇偶性下标配对的情况(此时其中留给方括号的长度为奇数),这时候是不可能产生号字符串的。因此$a=b$是有解的前提。

接下来我们说明如果$a=b$一定有解。实际上我们可以不断找到两个相邻的0出现的下标(忽略1出现的位置),其中一者是偶数,另外一者是奇数。之后我们将它们配对,并删除。重复这个过程我们就可以将$0$替换为圆括号。之后对$1$的替换就非常简单了。

因此答案为$\sum_{i=0}^{n/2} {n/2\choose i}^2$。

题目2:给定长度为$n$的序列$a$和序列$b$,之后要求找到一组权值最大的合法字符串。如果字符串的第$i$个字符是圆括号,则该位置的权值为$a_i$,否则为$b_i$,字符串的总权值就是所有位置的权值之和。其中$n$为偶数。

首先我们可以将所有位置都放置为方括号,之后我们考虑将一些位置替换为圆括号,我们定义$c_i=a_i-b_i$。

在题目1中我们已经讨论过圆括号中奇数下标和偶数下标数量相同是存在一种方案的等价条件。因此我们可以不断找到权重$c$最大的奇数下标和偶数下标$i,j$,如果$c_i+c_j\gt 0$,则将这两个下标替换为圆括号并重复流程,否则退出流程。

提供一道题目

最短合法括号子串

题目1:给定一个长度为$n$的括号序列,之后对于$i=1,\ldots,n$,分别找出以第$i$个字符开始最短的非空合法括号序列的长度,如果不存在则输出$-1$。

我们可以记R[i]表示以$i$开始最短非空合法括号序列的结束位置,则我们在处理R[i]的时候可以先将其设置为$i+1$,之后检查s[R[i]]是否是),如果不是,则将R[i]设置为R[R[i]]+1。重复这个操作即可。这是因为,如果一个括号序列不是(),则一定内部包含若干个不相交的合法括号子序列。

上面的过程的时间复杂度是$O(n)$。

统计合法的括号子串数

题目1:给定一个长度为$n$的括号序列,要求计算其中有多少非空子字符串(连续的),是一个合法的括号序列。

首先我们求出R[i],表示以$i$开始最短非空合法括号序列的结束位置。可以发现这时候如果我们将$i$的父亲设置为$R[i]+1$,那么可以发现这时候形成了一棵树,且树上某个顶点到其任意祖先的路径上的顶点序列对应一个合法的括号子串。因此答案为每个顶点的深度之和。

时间复杂度为$O(n)$。

题目2:在题目1的基础上。要求将结果去重,即两个不同的子串,其值相同,那么只需要统计一次。

一般统计字符串不同子串需要用到lcp或后缀自动机,而统计不同回文需要用到回文自动机。这边统计不同的合法括号子串,则也需要类似的方式来去重。

首先我们在题目1的基础上,构建出最终的树。之后我们考虑如何去重。我们可以通过SA算法求出lcp数组。之后为了保证仅统计一次,对应公共的子串,我们仅在处理较大后缀的时候计算一次。这时候就相当于询问在$right[j]>x$且满足$j$是顶点$i$的祖先的有多少个。这里可以使用倍增或持久化线段树来做。

这里时间复杂度和空间复杂度为$O(n\log_2n)$。