SP7866 ADV04G1 - Regular expressions (Hard)

正则表达式是一种用于定义字符串集合的表达方式。本题中的正则表达式仅由小写字母 a-z 和特殊符号‘?’、‘*’及‘+’组成。每个字母在定义的字符串中，对应其自身。特殊符号只能出现在某个字母之后，表示该字母的重复次数： - ‘?’ 表示该字母出现零次或一次 - ‘*’ 表示该字母出现零次或多次 - ‘+’ 表示该字母出现一次或多次

第一行输入一个整数 $T$，表示测试用例的数量。接下来描述 $T$ 个测试用例。每个测试用例的第一行是一个长度为 $L$ 的字符串 $S$。第二行是一个整数 $n$，表示正则表达式的数量。接下来的 $n$ 行中，每行给出一个正则表达式 $R_i$，你需要找到与之匹配的子串。

对于每个正则表达式，输出找到的匹配子串。如果找不到这样符合条件的子串，则输出 `-1`。 **本翻译由 AI 自动生成**