Regular expressions (Easy)#3181
Regular expression is an expression which defines a set of strings. In this problem, a regular expression will contain only small Latin letters - and special characters '?', '*', and '+'. Each letter corresponds to itself in the defined strings. A special character can occur only after some letter and indicates the number of repetitions of the letter:
For example, "ac", "abc", "acc", "abcccc", and so on, match the regular expression "ab?c+".
For the given string, find the substring which matches the given regular expression. If there are several such substrings, output the leftmost one in the original string. If there are still several, output the longest one.
The first line contains the number (1 \leq T \leq 100) — the number of test cases. Then test cases follow. The first line of each test case contains the string of length (1 \leq L \leq 200). The next line contains the integer (1 \leq n \leq 10) — the number of regular expressions. The next lines contain regular expressions R_i (1 \leq |R_i| \leq 20) for which you must find substrings in .
For each regular expression, output the matching substring, or if there is no such substring in the given string.
Example 1