/ Vijos / 题库 /

正则表达式简化版

正则表达式简化版

描述

在程序设计中,正则表达式(Regular Expressions)是用来处理复杂的字符串匹配以及模式识别问题的利器。正则表达式的一种常见用法是,给定一个正则表达式和一个字符串,然后询问给定的正则表达式能否匹配整个字符串,你需要处理的就是这种询问。

当然,编写一个优秀的正则表达式引擎是有难度的,在这道题目中,你需要编程处理一种经过高度简化的正则表达式。以下是这种正则表达式简化版的定义。

简化版的正则表达式可能包含以下字符:0~9的数字,A~Z以及a~z的大小写英文字母,下划线“_”,方括号“[”和“]”,花括号“{”和“}”,短横线“-”。其中,方括号和花括号一定以成对的方式出现且不会存在任何嵌套;短横线一定出现在方括号内,且短横线两边的字符或者同为数字,或者同为小写字母,或者同为大写字母,且短横线前面的字符的ASCII码不大于后面的字符;花括号内只会出现数字。下面将数字、英文字母和下划线统称为“普通字符”。

出现在括号外的普通字符即表示与字符串中同样的单个字符匹配,例如正则表达式“dd”可匹配字符串“dd”,但不能匹配“Dd”(因为大小写敏感),也不能匹配“dd_”(正则表达式中不存在与最后的“_”匹配的元素)。

成对的方括号以及之间的部分也匹配字符串中的单个字符,但可以匹配的单个字符是一个集合,这个集合包含方括号中间的普通字符。例如正则表达式“[Dd]d_engi”既能匹配“Dd_engi”又能匹配“dd_engi”;正则表达式“[AaB][aAb]”可匹配“Ab”“aA”“Ba”等,但不能匹配“AB”“bA”或“bB”;正则表达式“13[56789]”可匹配“135”“136”“137”“138”“139”中的任何一个,且不能匹配其它字符串。

成对的方括号间,除了普通字符外,也可能出现短横线“-”,表示与连续的一段字符匹配。例如,“[A-Z]”可匹配任何单个大写字符构成的字符串,如“E”“N”“G”“I”等;“[0-9]”可匹配任何单个数字构成的字符串;“[2-4A-Z]”可匹配2~4的数字或者大写字母,但不能匹配“1”“5”或者“a”;正则表达式“13[5-9]”、“13[85-79]”、“13[956-8]”、“13[5-78-9]”、“13[56789]”“13[98765]”“13[567898765]”“13[5-56-67-78-89-9]”互相之间都是等价的,都表示可匹配“135”“136”“137”“138”“139”中的任何一个,且不能匹配其它字符串。

成对的花括号内含一个整数,表示“前一元素的标准应重复匹配若干次”。例如,“D{2}”表示将字符D重复两次,匹配字符串“DD”;正则表达式“D{1}”与“D”等价;“D{11}”与“DDDDDDDDDDD”等价;“[Dd]{2}”可匹配“dd”“dD”“Dd”“DD”四种字符串;“dd_[eng]{3}i”可匹配“dd_engi”“dd_eeei”“dd_enni”“dd_eeni”“dd_gnei”等。成对的花括号的前面或者是普通字符或者是成对的方括号,不可能是另一对花括号。正则表达式“1[35][0-9]{8}”的意义是“第一位是1,第二位可以是3或5,后面有8个0~9的数字”,它可以用来匹配中国大陆的手机号码。

格式

输入格式

第一行是一个简化版的正则表达式。

以下若干行,每行一个字符串,直到文件结束,是对于第一行给定的正则表达式能否将其匹配的询问。

不会出现空字符串。

输出格式

对于第二行开始的每个字符串,根据能否进行匹配,输出一行“Regular Expression is Fun!”或者“Boring String Matching...”,不包括引号,其中的标点是英文标点(半角)。

样例1

样例输入1

[Dd]{2}_[eE][n-n][g_v][ii-jj]
dd_engi
Dd_engi
DD_envj
dD_eegi
dd-engi
ddengi
DD_Enhi

样例输出1

Regular Expression is Fun!
Regular Expression is Fun!
Regular Expression is Fun!
Boring String Matching...
Boring String Matching...
Boring String Matching...
Boring String Matching...

提示

每个输入文件不超过11行,大小不超过8KB;第二行起,每行不超过256个字符。

信息

ID
1416
难度
7
分类
字符串 | 表达式处理 点击显示
标签
(无)
递交数
302
已通过
60
通过率
20%
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

dd_engi 的 NOIP2008 模拟之狮子座