打卡信奥刷题（2756）用C++实现信奥题 P3719 [AHOI2017初中组] rexp

P3719 [AHOI2017初中组] rexp

题目背景

为了解决形形色色的字符串匹配问题，正则表达式是一个强有力的工具。正则表达式通过定义一套符号体系，能够表示出需要查找的字符串所具有的性质。如a|aa能匹配a或aa，(a|b)c能匹配ac或bc。

题目描述

完整的正则表达式过于复杂，在这里我们只考虑由(、)、|和a组成的正则表达式。运算遵循下列法则：

1. 有括号时，我们总是先算括号内的部分；

2. 当两个字符串（或由括号定义的子串）间没有符号时，我们总把它们连起来作为一个整体；

3. |是或连接符，表示两边的字符串任取其一，若同一层里有多个或连接符，可以看作在这些或连接符所分开的若干字符串里任取其一。

例如，(aaa)aa|aa|(a(aa)a)、(aaaaa)|(aa)|aaaa和aaaaa|aaaa|aa是等价的，它们都能匹配长度为2 , 4 2,42,4或5 55的全a字符串。

下面给定一个简化正则表达式，试编程计算它最多能匹配多长的全a字符串。

输入格式

输入一行一个合法的简化正则表达式。

输出格式

一行一个整数，表示能匹配的最长全a字符串长度。

输入输出样例 #1

输入 #1

(aaa)aa|aa|(a(aa)a)

输出 #1

5

输入输出样例 #2

输入 #2

((a|aaa)|aa)|a

输出 #2

3

输入输出样例 #3

输入 #3

(a(aa|aaa)a|(a|aa))aa

输出 #3

7

说明/提示

【数据范围】

对于20 % 20\%20%数据，表达式长度不超过100 100100，且不存在括号。

对于40 % 40\%40%数据，表达式长度不超过100 100100。

对于70 % 70\%70%数据，表达式长度不超过2 × 10 3 2 \times 10^32×103。

对于100 % 100\%100%的数据，表达式长度不超过10 5 10^5105。

保证表达式合法（即|两端和括号内运算结果均非空字符串）。

C++实现

#include<stdio.h>#include<string.h>inti=1;charch[100005];intwork(){intlen=0,t;while(1){i++;if(ch[i]==')'){returnlen;}//右括号必须写在前面if(ch[i]=='a')len++;if(ch[i]=='(')len+=work();if(ch[i]=='|'){t=work();return(len>t)?len:t;}//这个地方必须加return}}intmain(){scanf("%s",ch+1);intlen,num,sum=0,max=0;len=strlen(ch+1);while(i<=len){if(ch[i]=='a')sum++,i++;elseif(ch[i]=='('){num=work();sum=sum+num;}elseif(ch[i]=='|')if(sum>max)max=sum,sum=0,i++;elsesum=0,i++;elseif(ch[i]==')')i++;}printf("%d",(sum>max)?sum:max);return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容