[CTSC2004]数字搜索regular

时间限制:20s      空间限制:162MB

题目描述

HURRICANE小组最近接到了一个搜索文本的任务,即从一个由数字构成的长文本中,匹配满足指定条件的子串。搜索的条件采用形如‘(0+10*1)*10*’这样的正则表达式来描述。其中正则表达式的归纳定义如下: 1. 0, 1, …, 9,0*, 1*, …, 9*是正则表达式; 2. 如果A和B是正则表达式,则(A),A+B,AB,(A)*都是正则表达式; 3. 只有按以上方法构造出来的表达式才是正则表达式。 其中,A+B表示“或者”关系,AB表示“连接”关系,(A)*表示A的内容“重复”零次或者多次。比如正则表达式(12+3)(4+5)6*,就可以匹配以124,125,34,35之一开头,之后接零0个或任意多个6的字符串(例如字符串12566)。正则表达式(1+0)*可以匹配所有由0和1构成的字符串,或者是空串。如果一个正则表达式不能匹配空串,则称它是非空的。本题考虑的都是非空正则表达式。如果在给定文本的某一个位置,存在一个以该位置结束的子串,能够被给定的非空正则表达式匹配,则称该位置是可匹配的。现在HURRICANE小组接到的任务就是找出所有可匹配的位置。你能帮助他们完成这个任务么?【任务描述】你的程序需要根据给定的输入,给出符合题意的输出: 输入包括一个满足如上定义的正则表达式,以及一长串文本; 你需要根据输入的正则表达式及文本,找出文本中所有可匹配的位置; 你给出的输出需要包括所有可匹配的位置。


输入格式

第一行描述一个正则表达式,第二行为需要处理的文本:第一行的正则表达式包括由一个空格分开的两个部分:一个非负整数n(1≤ n≤ 10),表示我们所要考虑的数字集(即在正则表达式和文本中所出现的数字)是0, 1, …, n–1。接下来是一个正则表达式,它由{‘(‘, ’)’, ’+’, ’*’}中的4个符号和{0, …, n–1}中的数字构成,表达式的长度不超过500个字符。第二行为一个由0到n-1之间数字构成的字符串,为需要处理的文本。该文本长度不超过10,000,000个字符。


输出格式

输出只有一行,包括一些由空格分开的整数,按从小到大的顺序依次输出所需处理的文本中每一个可匹配的位置。


样例输入

4 12333+33
312331
说明:对于输入示例,需要处理的文本是’312331’,其中只有第5个字符所在的位置(下划线所在处)是可匹配的。这时正则表达式’12333+33'中的’33’可以与之匹配。


样例输出

5

提示

【评分方法】
本题目一共有十个测试点,每个测试点的分数为总分数的10%。对于每个测试点来说,如果你给出的答案正确,那么你将得到该测试点全部的分数,否则得0分。
提示:在本次的测试数据中,有6个测试点中的正则表达式不出现’*’,其中有3个测试点,正则表达式只由数字和’+’构成。有一个测试点的待处理文本不超过1,000,000个字符。该题有严格的时间限制,请尽量优化你的算法。


题目来源

没有写明来源