BZPRO

#1161. [CTSC2004]数字搜索regular

内存限制：162 MiB 时间限制：20 Sec
提交 提交记录 讨论

题目描述

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个字符。该题有严格的时间限制，请尽量优化你的算法。

BZPRO Powered by Remmina.
Github Repository