#P2003. ACSL 2015-2016 Junior Division Contest #4 ACSL Reg Exp
-
ID: 929
Type: Default
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: 1
Uploaded By:
ZihanShen
Tags> ACSL 2015-2016 Junior Division Contest #4 ACSL Reg Exp
题目描述
正则表达式与有限状态自动机（FSA）是 ACSL 的一个类别，但在初级组（Junior Division）中不进行测试。不过这里将其作为一道编程题使用，用来展示如何把一个长字符串或多个字符串用更精简的形式表示。正则表达式的概念最早由 Stephen Kleene 在 20 世纪 50 年代形式化。下面将使用以下运算：
| 运算符 | 含义与示例 |
|---|---|
| ? |
表示其前面的元素出现 0 次或 1 次。 例：colou?r 匹配 color 和 colour。 |
| * |
表示其前面的元素出现 0 次或多次。 例：ab*c 匹配 ac、abc、abbc、abbbc 等。 |
| + |
表示其前面的元素出现 1 次或多次。 例：ab+c 匹配 abc、abbc、abbbc 等，但不匹配 ac。 |
输入格式
将有 行输入。第一行包含 个字符串。后 行每行包含一个合法的正则表达式字符串。每个正则表达式长度不超过 个字符，且运算符不超过两个。
输出格式
对于每个正则表达式，输出所有与其匹配的字符串；如果没有任何字符串匹配，则输出 NONE。这里用 # 表示空字符串。
输入输出样例
输入 #1
#, a, aa, aaa, ab, abb, aabb, aaab, abbb, b
a?b
a*b
a+b
a*b+
a?b+
输出 #1
ab, b
ab, aaab, b
ab, aaab
ab, abb, aabb, aaab, b, abbb
ab, abb, abbb, b