题面描述:

塔子哥在学习编译原理课程时需要将C语言翻译成汇编程序，为此他决定使用正则表达式来完成文本的切词任务。已知一种字符串解析语法，包括N匹配单个数字(0-9)，A匹配单个字母(a-z或A-Z)，以及n(...)表示分组，其中分组包含至少一个N或A，n是一个数字，表示该分组重复的次数(1<=n<=200)。输入包括两行，第一行为解析语法，第二行为目标字符串。要求找到第一个匹配解析语法的子字符串并输出，如果没有匹配到则输出!。

思路：模拟+KMP

本题的模式串可以展开，使用栈来模拟即可，每次一个(放入栈中对应的位置以及前面的数量，每次)弹出栈顶元素，然后将栈顶元素的数量乘以当前的字符串加上栈顶元素的前面的字符串加入到模式串中即可。

需要注意有可能模式串非常长，所以中间需要判断是否已经超过了匹配串的长度，超过则直接返回。

题目描述

$\qquad$小明这学期有一门压力巨大的专业课，编译原理，这到底是谁在听懂啊？啊？！还要做恁多实验。有一个实验要求小明将C语言翻译成对应的汇编程序，这就需要对文本进行切词，聪明的小明决定使用正则表达式来完成切词任务。

$\qquad$已知存在种字符串解析语法,其中的语法元素如下

$\qquad$ N：用于匹配单个数字(0-9)

$\qquad$ A：用于匹配单个字母(a-z，A-Z)

$\qquad$ n()：用于表示一个分组，分组中至少有一个N语法元素或者A语法元素，n为个数值,表示匹配n次，1<=n<=200

$\qquad$ 输入给定的解析语法和字符串，要求从中找到第一个满足解析语法的字符串。

输入描述

$\qquad$输入两行数据，第一行是给定的解析语法，第二行是目标字符串。

输出描述

$\qquad$输出匹配的子字符串内容，如果没有匹配中任何字符串，输出!（英文感叹号）

样例一

输入

2(AN)
BA3A3ABB

输出

A3A3

样例二

输入

2(A2(N))
A3322A33P20BB

输出

A33P20

Limitation

1s, 1024KiB for each test case.