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 "\". |
Note:
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 [ ].
Input
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.
Output
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.
Sample Input
2 1 Hello world! 2 He.*d! He*d! 1 Sunny Cup 1 Sunny Cup
Sample Output
Case #1: Hello world! -------------------------------------------- No match is found -------------------------------------------- Case #2: Sunny Cup --------------------------------------------Submit
Source: Zhejiang University Local Contest 2003