企业官网建设流程全解析

106. 正则问题（分治）

2017年蓝桥杯省赛 - 正则问题（困难）

标签：2017省赛分治

题目描述

考虑一种简单的正则表达式：只由x()|组成。小明想求出这个正则表达式能接受的最长字符串的长度。

例如((xx|xxx)x|(x|xx))xx能接受的最长字符串是xxxxxx，长度是 6。

输入描述

一个由x()|组成的正则表达式，输入长度不超过 100，保证合法。

输出描述

这个正则表达式能接受的最长字符串的长度。

输入输出样例

示例：

输入

((xx|xxx)x|(x|xx))xx

输出

6

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

解题思路

表达式里只有x()|四种符号，含义都能翻译成"长度"：x是一个字符；a|b二选一，取较长的一支；两个部分挨在一起是连接，长度相加；()只是分组，不影响长度。题目要的是整个表达式能拼出的最长串，所以只要按这些规则把表达式化成一个数字。

把样例((xx|xxx)x|(x|xx))xx画成树，图上|节点两端取大、+节点两端相加，每个节点下方标出该子树能拼出的最长长度，根节点的 6 就是答案：

括号有嵌套，外层的长度依赖内层，所以从最内层开始化简最稳妥：反复找最里面的(...)，把它里面的内容按|拆开、取最长的一段替换回去，一层层把括号消掉。最后若顶层还剩|，照样取最长的一段。

拿样例((xx|xxx)x|(x|xx))xx走一遍，从最内层括号开始逐层化简：

((xx|xxx)x|(x|xx))xx ↓ 最内层 (xx|xxx) 取最长，得 xxx，接上后面的 x (xxxx|(x|xx))xx ↓ 最内层 (x|xx) 取最长，得 xx (xxxx|xx)xx ↓ 括号内 xxxx|xx 取最长，得 xxxx，再接上末尾的 xx xxxxxx → 长度 6

代码实现

s=input()defkh(s):# 反复化简最内层的括号while')'ins:r=s.find(')')# 最靠左的右括号，它属于最内层括号l=r-1whilel>=0:ifs[l]=='(':# 配对的左括号# 括号内按 | 拆开，取最长的一段替换回去p=s[l+1:r].split('|')s=s[:l]+max(p,key=len)+s[r+1:]breakl-=1returns s=kh(s)# 顶层可能还剩 |if'|'ins:s=max(s.split('|'),key=len)print(len(s))

复杂度分析

• 时间复杂度：O(n2)O(n^2)O(n2)，nnn是输入长度（≤100\le 100≤100）。每消掉一对括号都要做一次全串查找和拼接，最坏有O(n)O(n)O(n)对括号。
• 空间复杂度：O(n)O(n)O(n)，化简过程中会不断生成新的字符串。