正则问题
2019-03-18 本文已影响0人
smatrcHendsa
经典的递归DFS 我对递归的理解不够深啊
看到括号 应该很轻松的想到是经典的递归问题 然后只有四个符号()x| 分别判断 就行了 要考虑多个||||||中间不同的元素的处理
问题描述
考虑一种简单的正则表达式:
只由 x ( ) | 组成的正则表达式。
小明想求出这个正则表达式能接受的最长字符串的长度。
例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是: xxxxxx,长度是6。
输入格式
一个由x()|组成的正则表达式。输入长度不超过100,保证合法。
输出格式
这个正则表达式能接受的最长字符串的长度。
样例输入
((xx|xxx)x|(x|xx))xx
样例输出
6
数据规模和约定
峰值内存消耗(含虚拟机) < 256M
CPU消耗 < 1000ms
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
string str;
int si, crt;
int dfs() {
int cnt = 0, mx = 0;
//sum是所有的加起来 cnt的单次的
while (crt < si) {
char c = str.at(crt);
if (c == '(') {
crt++;
cnt += dfs();
}
else if (c == 'x') {
cnt++;
crt++;
mx = max(mx, cnt);
}
else if (c == '|') {
mx = max(mx, cnt);
cnt = 0;
crt++;
}
else {
crt++;
break;
}
}
mx = max(mx, cnt);
return mx;
}
int main() {
cin >> str;
si = str.size();
cout << dfs() << endl;
return 0;
}