[CTSC2004]数字搜索regular

HURRICANE 小组需要在一段由数字构成的长文本中，寻找满足指定条件的子串。搜索条件使用类似 (0+10*1)*10* 的正则表达式描述。

正则表达式按照以下规则递归定义：

其中：

例如，正则表达式 (12+3)(4+5)6* 可以匹配以 124、125、34、35 之一开头，之后接零个或任意多个 6 的字符串，如 12566。

正则表达式 (1+0)* 可以匹配所有仅由 0 和 1 构成的字符串，也可以匹配空串。如果一个正则表达式不能匹配空串，则称它是非空正则表达式。本题只考虑非空正则表达式。

对于给定文本中的某个位置，如果存在一个以该位置结尾的子串，能够被给定的非空正则表达式匹配，则称该位置是可匹配的。

请找出文本中所有可匹配的位置。

输入格式

输入共两行。

第一行包含一个非负整数 $n$ 和一个正则表达式，二者之间以一个空格分隔。整数 $n$ 表示正则表达式和文本中使用的数字集合为 $\{0,1,\ldots,n-1\}$ 。

正则表达式由符号 (、)、+、* 和数字集合 $\{0,1,\ldots,n-1\}$ 中的数字组成。

第二行包含一个仅由 $\{0,1,\ldots,n-1\}$ 中数字构成的字符串，表示需要处理的文本。

输出一行，包含若干个以空格分隔的整数，按照从小到大的顺序输出文本中所有可匹配的位置。

4 12333+33
312331

需要处理的文本为 312331，其中只有第 $5$ 个字符所在的位置是可匹配的。正则表达式 12333+33 中的 33 可以匹配以该位置结尾的子串。

$1\le n\le 10$ ；
正则表达式的长度不超过 $500$ 个字符；
文本长度不超过 $10^7$ 个字符；
本题共有 $10$ 个测试点，每个测试点占总分的 $10\%$ ；
有 $6$ 个测试点的正则表达式中不出现 *；
其中有 $3$ 个测试点的正则表达式只由数字和 + 构成；
有 $1$ 个测试点的文本长度不超过 $10^6$ 个字符；
数据保证按要求输出全部可匹配位置时，输出总长度不超过 $64\ \mathrm{MB}$ ；测试数据中最大的正确输出约为 $4.2\ \mathrm{MB}$ 。

本题为 CTSC 2004 试题「数字搜索regular」，题面与测试数据整理自 BZOJ。

4 12333+33
312331