Welcome to ZOJ
Select Problem
ZOJ Problem Set - 1632
Advanced Regular Expression

Time Limit: 10 Seconds      Memory Limit: 32768 KB

Given a paragraph and several regular expressions, your task is to find the first match of each regular expression. If multiple matches exist, you must output the longest one.

The regular expression can contain some meta-characters described below:

* Matches the preceding character/meta-character zero or more times.
+ Matches the preceding character/meta-character one or more times.
? Matches the preceding character/meta-character zero or one time.
. Matches any single character.
[xyz] A character set. Matches any characters within the brackets.
[^xyz] A negative character set. Matches any characters NOT within brackets.
\d Matches a digit character.
\D Matches a non-digit character.
\a Matches a alpha character.
\A Matches a non-alpha character.
\n Matches a new-line character. (ASCII 10)
\s Matches any white-space character including space, tab and new-line.
\S Matches any non-white-space character.
\t Matches a tab character. (ASCII 9)
\w Matches an alphanumeric character (including "_")
\W Matches a non-alphanumeric character.
\* Matches "*".
\+ Matches "+".
\? Matches "?".
\. Matches ".".
\[ Matches "[".
\] Matches "]".
\\ Matches "\".

1. [ ] always appear in pairs and will not be nested.
2. The character set within [ ] will not be empty.
3. Meta-characters can not be used within [ ].


The first line of input contains an integer n, the number of test cases. Each test case begins with an integer L, and the following L lines give the paragraph. The next line contains an integer m, with the following m lines containing a regular expression each.

You can assume that each paragraph contains no more than 100,000 characters and each regular expression has no more than 100 characters.


For each test case, first print the case number on a single line, then print the match for each regular expression. If no match is found, print "No match is found". Print a blank line after each test case.

Always print a '\n' after each match unless the match ends with a '\n' itself. Print a line with 44 dashes after each match.

Empty match is NOT valid.

Some Examples:
m.n matches "man", "men", "min" but not "moon".
Te+st matches "test", "teest", "teeeest" etc. BUT NOT "tst".
Te*st matches "test", "teest", "teeeest" etc. AND "tst".
[aeiou] matches every lowercase vowel.
[,.?] matches a literal ",", "." or "?".
[^^] matches any character except "^".

Sample Input

Hello world!
Sunny Cup
Sunny Cup

Sample Output

Case #1:
Hello world!
No match is found

Case #2:
Sunny Cup

Author: XU, Chuan
Source: Zhejiang University Local Contest 2003
Submit    Status