akyu. Gensokyo Forbidden Words

akyu. Gensokyo Forbidden Words

ZOJ3373. 幻想乡禁句

downloadsource code (ZOJ3373.cpp) [通配符(glob), 正则表达式(regex), 字符串(string), if-else]

本题的主角是幻想乡的记忆——稗田阿求,描述和样例中还有PAD长,笨蛋⑨和隙间大妈的友情路过。不过不知道大家注意到没有,本题最大的捏它其实是标题吶,Gensokyo Forbidden Words取其首字母便是大名鼎鼎的ジー・エフ・ダブリュ(即使不识平假名的你也懂的!)。灵感也来自当时在Google Reader看到的一则与ジー・エフ・ダブリュ之父有关的正则比赛和ジー・エフ・ダブリュ要升级的有关猜测。

  • 幻想鄉的記憶/稗田阿求(ひえだ の あきゅう)

题目介绍了模式匹配中的两大家族,常在终端下生活的人怎么可能不熟悉的文件通配符glob,还有文本处理,包括修改代码的利器正则表达式regex。题目其实就是要求把输入的glob通过最naive的方式转成输出的regex,题目描述给出了glob和regex的规则,而如何转换则需要自己推出来。(参考sample)

注意题目里对输入数据做了很多的保证,所以最后的转换规则是很简单的,无非[...]外的”.”变成”[.]“,”?”变成”.”,”*”变成”.*”,而对于[...]内的字符,如果第一个字符是”!”,那么变成”^”,其它不变。注意[...]和[!...]内应该是非空的,也就是如果第一个字符就是’]',那么这个’]'并不是与’[‘匹配的,这个在More Sample Input/Output里很好的说明了。if-else题其实也不简单的,一手抖就WA了。

题目强调了测试数据extremely large,所以如果用cin/cout就很可能超时,而且除了人肉的小case,只有一个超大的case,如果数组开小了,很可能会数组越界从而Runtime Error/Segmentation Fault,最好用getchar()。还有空格/TAB/空行注意。





©2010 Zhejiang University ACM/ICPC Team
©2010 http://watashi.ws/acm_x_touhou/

10 Responses to “akyu. Gensokyo Forbidden Words”
  1. CrazyCow says:

    [^A] 应该输出[^][A]吧?

  2. 游客 says:

    嗯,扯远了…也就是说单论此题是不考虑嵌套的,不过不熟悉glob的人单从题面似乎真不容易看出这点来。

    • watashi says:

      嗯,对于熟悉glob和regex的人来说就是秒杀,否则题目都得读好长,sample又得看好长
      描述里面的东西其实基本都是搬运文档和wiki了……

  3. 游客 says:

    请问 [![![!a]]] 这个数据应该输出 [^[![!a]]] 还是 [^[^[^a]]] 呢?按你的算法和程序是前者,但是我觉得是后者,后者为什么不对呢?

  4.  
Leave a Reply