#P1161. [CTSC2004]数字搜索regular

    ID: 167 传统题 2000ms 256MiB 尝试: 164 已通过: 14 难度: 8 上传者: 标签>CF2400提高+/省选-递归下降语法分析Thompson 构造传递闭包子集构造位集求并哈希表

[CTSC2004]数字搜索regular

[CTSC2004] 数字搜索

题目背景

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小组接到的任务就是找出所有可匹配的位置。你能帮助他们完成这个任务么?

题目描述

你的程序需要根据给定的输入,给出符合题意的输出:

  • 输入包括一个满足如上定义的正则表达式,以及一长串文本;
  • 你需要根据输入的正则表达式及文本,找出文本中所有可匹配的位置;
  • 你给出的输出需要包括所有可匹配的位置。

输入格式

输入文件regular.in的第一行描述一个正则表达式,第二行为需要处理的文本:

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

输出格式

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

样例 #1

样例输入 #1

4 12333+33
312331

样例输出 #1

5

提示

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

**提示:**在本次的测试数据中,有6个测试点中的正则表达式不出现’*’,其中有3个测试点,正则表达式只由数字和’+’构成。有一个测试点的待处理文本不超过1,000,000个字符。

本站当前数据版本的自动机结构范围

本题原始表达式和文本长度界仍保留。另明确当前教学数据的结构条件:按随题解的标准Thompson构造(每个数字、并、星号各使用起终节点,连接用epsilon边),每次转移后并入起点epsilon闭包以同时考虑所有后缀起点。在给定文本上懒构造子集自动机时,实际遇到的不同“状态子集、下一位数字”转移组合总数不超过100000。

这是本站当前已安装10组原数据全量核验后的补充,不冒称原CTSC提供了这个保证,也不把正则表达式一般情形的可达子集数量误称为多项式。原数据最大NFA状态918、最大实际可达子集67473、最大首次转移91594;扩容后的缓存不再溢出。