DFSBFSA*递归搜索暴力破解

正则问题

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;
}
上一篇下一篇

猜你喜欢

热点阅读