题目描述

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

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

题面描述:

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

思路：模拟+KMP

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

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