#PQJ2711x15588. QOJ 2711_15588

    ID: 2853 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:CTSC 2004字符串

QOJ 2711_15588

清华大学 中国国家队选拔赛2004 2004-05-09 数字搜索 (regular) 【背景描述】 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小组接到的 任务就是找出所有可匹配的位置。你能帮助他们完成这个任务么? 【任务描述】 你的程序需要根据给定的输入,给出符合题意的输出: z 输入包括一个满足如上定义的正则表达式,以及一长串文本; z 你需要根据输入的正则表达式及文本,找出文本中所有可匹配的位置; z 你给出的输出需要包括所有可匹配的位置。 【输入格式】:(regular.in) 输入文件regular.in的第一行描述一个正则表达式,第二行为需要处理的文本: z 第一行的正则表达式包括由一个空格分开的两个部分: „ 一个非负整数n(1≤ n≤ 10),表示我们所要考虑的数字集(即在正则 表达式和文本中所出现的数字)是0, 1, …, n–1。 „ 接下来是一个正则表达式,它由{‘(‘, ’)’, ’+’, ’’}中的4 个符号和 {0, …, n–1}中的数字构成,表达式的长度不超过500 个字符。 z 第二行为一个由0 到n-1 之间数字构成的字符串,为需要处理的文本。 第 四 页 共 九 页 清华大学 中国国家队选拔赛2004 2004-05-09 该文本长度不超过10,000,000 个字符。 【输入样例】 4 12333+33 说明:对于输入示例,需要处理的文本是’312331’,其中 312331 只有第5 个字符所在的位置(下划线所在处)是可匹配的。 这时正则表达式’12333+33'中的’33’可以与之匹配。 【输出格式】:(regular.out) 输出文件只有一行,包括一些由空格分开的整数,按从小到大的顺序依次输 出所需处理的文本中每一个可匹配的位置。 【输出样例】 5 【运行限制】 运行时间 2 秒 内存使用 64M 【有关语言方面的提示】 对于使用C++选手来说,用ifstream 读取数据是一个很慢的过程,可能会消 耗大量的时间。所以我们建议使用fread/fgetc/fscanf 读取数据,并使用setbuf 设 置缓存。另,fscanf(file, “%c”, &c)的速度经过测试表现也比较慢,可以使用 fgetc(file)代替。 对于使用Pascal 的选手来说,可以用SetTextBuf 设置缓存来加快读取文件的 速度。也可以考虑使用BlockRead 来读取文件。 【评分方法】 本题目一共有十个测试点,每个测试点的分数为总分数的10%。对于每个测 试点来说,如果你给出的答案正确,那么你将得到该测试点全部的分数,否则得 0 分。 提示:在本次的测试数据中,有6 个测试点中的正则表达式不出现’*’,其中 有3 个测试点,正则表达式只由数字和’+’构成。有一个测试点的待处理文本不 超过1,000,000 个字符。该题有严格的时间限制,请尽量优化你的算法。 第 五 页 共 九 页