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

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代码实现sinput()defkh(s):# 反复化简最内层的括号while)ins:rs.find())# 最靠左的右括号它属于最内层括号lr-1whilel0:ifs[l](:# 配对的左括号# 括号内按 | 拆开取最长的一段替换回去ps[l1:r].split(|)ss[:l]max(p,keylen)s[r1:]breakl-1returns skh(s)# 顶层可能还剩 |if|ins:smax(s.split(|),keylen)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)化简过程中会不断生成新的字符串。