递归与回溯_正则问题()|x

acwing 1225 正则问题（递归回溯）

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

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

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

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

思路：遇到 '(' '|' 就进行递归，遇到 ')' 就进行回溯，每次递归 dfs() 计算的是该次递归所遇到的所有 '*' 的数目

注意：由于是对字符串进行递归，每次遇到一个符号都要进行索引指针+1，但是可能由 '|' 进行多次的递归调用，而在一个 ')' 处回溯，
所以在 ')' 处不能进行索引指针的自增（因为可能会自增好多次），正确的应该是由对应递归的发起者进行负责回溯点的索引指针的自增。

#include<iostream>

using namespace std;
string str;
int k=0;

int dfs()
{
    int n=str.size();
    int res=0;
    while(k<n)
    {
        if(str[k]=='(')
        {
            k++;
            res+=dfs();
            k++;
        }
        else if(str[k]=='|')
        {
            k++;
            res=max(res,dfs());
        }
        else if(str[k]==')')
        {
            //k++;
            break;
        }
        else 
        {
            res++,k++;
        }
    }
    return res;
}

int main()
{
    cin>>str;
    cout<<dfs();
}