题目描述

考虑一种简单的正则表达式：

只由 x ( ) | 组成的正则表达式。

小明想求出这个正则表达式能接受的最长字符串的长度。

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

样例

输入

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

输出

6

思路：假如字符串里没有括号，仅包含x|，相当于把由xxxx构成的字符串用|分割成n份，要我们选出这n份中最长的一份，这当然非常简单。再考虑有括号的情况，把一对()中的字符串单独拿出来看并计算出这一部分的最长连续x的个数res0，相当于将()所包含的字符串替换成res0个连续的x，递归处理每一对()将它们消除，即可简单的计算出答案。
虽然是递归做，但每个字符只遍历了一遍故时间复杂度为O(n)。

C++ 代码

#include<iostream>
using namespace std;
string s;
int n;
int dfs(int &pos){  //pos表示当前位置，传引用方便修改外层递归的参数
    int res = 0, cur = 0;   //res存当前区间的结果，cur记录目前的连续x的长度
    for(int i = pos; i < n; i++){
        if(s[i] == 'x') cur ++;
        else if(s[i] == '|'){
            res = max(res, cur);
            cur = 0;
        }
        else if(s[i] == '('){   //当遇到左括号，递归计算该对括号所包含的区间的答案
            i++;
            cur += dfs(i);      
            continue;
        }
        else if(s[i] == ')'){   //当遇到右括号说明当前区间答案计算完毕，更新外层递归的指针位置
            pos = i ;
            break;
        }
    }
    res = max(res, cur);
    return res;
}
int main(){
    cin >> s;
    n = s.size();
    int start = 0;
    int ans = dfs(start);
    cout << ans;
    return 0;
}