竞赛算法(11) 字符串

正则括号序列#

建议看cp-algorithm Balanced bracket sequences

正则括号序列(Regular Bracket Sequence, RBS)或称平衡括号序列(Balanced Bracket Sequence, BBS), 指的是某种合法的括号序列. 通常定义为加上数字和运算符之后能够得到合法表达式的括号序列. 其递归定义如下:

空串是RBS
若 $t$ 是RBS, $(t)$ 也是RBS.
若 $s$ 是RBS, $t$ 是RBS, 则 $st$ 是RBS.

RBS的第一个括号一定是左括号, 而第一个括号一定对应且仅对应一个右括号. 所以, 所有的RBS一定可以被表示为 $(s)t$ , 这种表示方式唯一. $s(t)$ 同理.

比如说 $(())()$ 是RBS, 而 $())($ 不是. alt text

正则括号序列的性质#

我们可以定义括号序列的平衡度: 左括号数量减去右括号数量. 可以非常简易地计算平衡度以及前缀平衡度: 我们给所有左括号赋1, 右括号赋-1, 则前缀和即为前缀平衡度, 总和即为总平衡度.

比如计算(())()的前缀平衡度:

赋值, 1, 1, -1, -1, 1, -1
做前缀和, 1, 2, 1, 0, 1, 0. 即为前缀平衡度.

再来计算())(的前缀平衡度:

赋值, 1, -1, -1, 1
做前缀和, 1, 0, -1, 0.

正则括号序列的核心性质(充要条件): 其总平衡度为0, 且前缀平衡度均大于等于0. 比如(())()的平衡度满足这个条件, 是RBS; ())(的前缀平衡度中出现了-1, 不满足这个条件, 不是RBS.

这个性质有一个非常巧妙的应用: 既然RBS的前缀平衡度均大于等于0, 我们就可以把他直接塞进dp状态里面, 这样转移出来的平衡度就会都满足前缀平衡度大于等于0. 只需要判断末尾平衡度是否等于0即可.

例题: 2191D2

正则括号序列的判定#

如果只有一种括号, 我们直接使用上面的充要条件即可.

如果涉及多种括号, 我们需要另一种判定方法:

建立栈st, 储存所有左括号.
遇到右括号时检查栈顶是否合法, 合法即弹出, 不合法直接返回false即可.
最后判定栈是否为空, 不为空返回false.
返回true

长度为n的RBS个数#

奇数为0, 偶数为卡特兰数 $C_{n/2}$ .

另一方面, 我们可以使用线性dp来计算.

设dp[i]表示长度为i的RBS个数. 则我们知道dp[i]一定可以被表示为 $(s)t$ 的形式. 于是, 我们枚举s和t的长度即可. 注意空串只有一种.

转移方程为

dp[i] = \sum_{j = 0}^{n - 2}dp[j]dp[i - 2 - j]

初始值dp[0] = 1.

寻找下一个字典序的RBS#

注意字典序(小于), 要寻找下一个字典序的RBS, 我们需要找到所有可以更改的(中, 最右边的那个. 我们可以从右往左遍历: 找到最右边的前缀平衡度大于等于2的(位置, 然后将该位置替换为), 把该位置之后的串删除. 然后再从这个位置往右贪心地填剩下的括号(右侧字典序最小): 先计算还需要填多少个左括号和右括号, 然后先全部填左括号, 再全部填右括号.

1
bool next_balanced_sequence(string & s) {
2
    int n = s.size();
3
    int depth = 0;
4
    for (int i = n - 1; i >= 0; i--) {
5
        if (s[i] == '(')
6
            depth--;
7
        else
8
            depth++;
9

10
        if (s[i] == '(' && depth > 0) {
11
            depth--;
12
            int open = (n - i - 1 - depth) / 2;
13
            int close = n - i - 1 - open;
14
            string next = s.substr(0, i) + ')' + string(open, '(') + string(close, ')');
15
            s.swap(next);
16
            return true;
17
        }
18
    }
19
    return false;
20
}

代码来自cp-algorithm

寻找所有长度为n的RBS#

从字典序最小的RBS开始, 即(((…))). 依次增加字典序即可.

判断当前RBS字典序排名, 寻找第k小字典序#

不赘述, 见cp-algorithm的相关内容.