#101161. [BZOJ 1161] [CTSC2004]数字搜索regular

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

是正则表达式；

如果 和 是正则表达式，则 都是正则表达式；

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

其中， 表示「或者」关系， 表示「连接」关系， 表示 的内容「重复」零次或者多次。

比如正则表达式 ，就可以匹配以 之一开头，之后接零 个或任意多个 的字符串（例如字符串 ）。正则表达式 可以匹配所有由 和 构成的字符串，或者是空串。如果一个正则表达式不能匹配空串，则称它是非空的。本题考虑的都是非空正则表达式。

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

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

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

一个非负整数 ，表示我们所要考虑的数字集（即在正则表达式和文本中所出现的数字）是 。

接下来是一个正则表达式，它由 中的 个符号和 中的数字构成，

第二行为一个由 到 之间数字构成的字符串，为需要处理的文本。

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

样例输入 #1

4 12333+33
312331

样例输出 #1

5

样例解释

需要处理的文本是 ，其中只有第 个字符所在的位置（下划线所在处）是可匹配的。这时正则表达式 中的 可以与之匹配。

对于 的数据，，表达式的长度不超过 ，文本长度不超过 个字符。

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