bzoj#P1161. [CTSC2004]数字搜索regular

[CTSC2004]数字搜索regular

题目描述

HURRICANE 小组最近接到了一个搜索文本的任务,即从一个由数字构成的长文本中,匹配满足指定条件的子串。搜索的条件采用形如 (0+101)10‘(0+10*1)*10*’ 这样的正则表达式来描述。其中正则表达式的归纳定义如下:

0,1,,90,1,,90, 1, \cdots , 9,0*, 1*, \cdots, 9* 是正则表达式;

如果 AABB 是正则表达式,则 (A)A+BAB(A)(A),A+B,AB,(A)*都是正则表达式;

只有按以上方法构造出来的表达式才是正则表达式。

其中,A+BA+B 表示「或者」关系,ABAB 表示「连接」关系,(A)(A)* 表示 AA 的内容「重复」零次或者多次。

比如正则表达式 (12+3)(4+5)6(12+3)(4+5)6*,就可以匹配以 124,125,34,35124, 125, 34, 35 之一开头,之后接零 00 个或任意多个 66 的字符串(例如字符串 1256612566)。正则表达式 (1+0)(1+0)* 可以匹配所有由 0011 构成的字符串,或者是空串。如果一个正则表达式不能匹配空串,则称它是非空的。本题考虑的都是非空正则表达式。

如果在给定文本的某一个位置,存在一个以该位置结束的子串,能够被给定的非空正则表达式匹配,则称该位置是可匹配的。现在HURRICANE 小组接到的任务就是找出所有可匹配的位置。你能帮助他们完成这个任务么?

输入格式

第一行描述一个正则表达式,第二行为需要处理的文本。

第一行的正则表达式包括由一个空格分开的两个部分:

一个非负整数 nn,表示我们所要考虑的数字集(即在正则表达式和文本中所出现的数字)是 0,1,,n10, 1, \cdots, n–1

接下来是一个正则表达式,它由 {(,),+,}\{(, ), +, *\} 中的 44 个符号和 {0,,n1}\{0, \cdots, n–1\} 中的数字构成,

第二行为一个由 00n1n-1 之间数字构成的字符串,为需要处理的文本。

输出格式

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

4 12333+33
312331
5

样例解释

需要处理的文本是 312331312331,其中只有第 55 个字符所在的位置(下划线所在处)是可匹配的。这时正则表达式 12333+3312333+33 中的 3333 可以与之匹配。

数据规模与约定

对于 100%100\% 的数据,1n101 \le n \le 10,表达式的长度不超过 500500,文本长度不超过 10710^7 个字符。

1010 个测试点。有 66 个测试点中的正则表达式不出现 *,其中有 33 个测试点,正则表达式只由数字和 ++ 构成。有一个测试点的待处理文本不超过 10610^6 个字符。该题有严格的时间限制,请尽量优化你的算法。