Regular expressions (Hard)#3182
Regular expressions are expressions that define a set of strings. In this problem, regular expressions consist of lowercase Latin letters – and the special characters , , and . Each letter matches itself in the described strings. A special character can occur only after a letter and denotes the number of repetitions of that letter:
For example, the strings "ac", "abc", "acc", "abcccc", and so on, match the regular expression "ab?c+".
In the given string, find the substring which matches the given regular expression. If there are several such substrings, output the one that appears first (the leftmost) in the string. If there are multiple such substrings, output the longest one.
The first line contains (1 \le T \le 100) — the number of test cases. Then test cases follow. The first line of each test case contains the string of length (1 \le L \le 200). The next line contains an integer (1 \le n \le 10) — the number of regular expressions. The next lines contain regular expressions R_i (1 \le |R_i| \le 100).
For each regular expression, output the corresponding matching substring, or -1 if such a substring does not exist.
Example 1