gougou1033

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

1033
Pattern Matching Using Regular Expression

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1448

1 2006-07-27 03:02:55 00:00:13 900K C++ glimpse

   这道题就是个纸老虎，看上去复杂，真正做起来是很简单的。字符串分析+dfs（动态规划）都可以AC。

   首先是对regular expression的分析。通过对题目的分析，我们不难发现，我们可以将regular expression分成n个block，这些block互相独立。一个block由两个部分组成。

1. 可以匹配的字符，ascii：0-255。遇到‘\’就从255个字符里删掉。

2. 匹配的格式。‘+’，‘*’和只需要匹配一次三种。

  分别以matchde string的第1位到第i位为起点Dfs这n个block，记录下可以匹配的最长长度和位置。因为block之间无关系，match的时候可以用动态规划求解。

上述的代码200行就可以搞定。不过这题有两个trick：

~~1． regular expression可以为空，返回无法匹配~~

~~2． 可能出现i+*j的情况，一个字符后有n个表示次数的符号，忽略后面n-1个~~

----

上面的trick2不存在，经我assert，re格式还是很规范的。

trick1确实存在，不过其实更一般的，这里的正则不允许匹配一个空串，这与我们所熟悉的正则不同，题目和sample也没有说明，这是很不厚道的。

更不厚道的是，[T-F]并不是什么都不匹配，而是等价于[F-T]，描述用了暧昧的between，而sample完全消不了歧义。

最后，最恶心人的地方。这题有很容易引起麻烦的不在0~127范围的ASCII码。由于char是signed char还是unsigned char是没有标准的，通常正则里比较，总是认为那些编码大于127（从来没有人说编码小于0）的字符排序在后面。但这题就是与常识相背，得用signed char。

大家要引以为戒，如果暑期集训谁这么不厚道的做暧昧的描述（“能够自圆其说，但却处处是坑“，注意我们不是在做考研英语阅读理解），并且数据出得这么不厚道。那么先拿出去tjjtds三分钟，再bg全集训队吧。

1033

Pattern Matching Using Regular Expression

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1448

1 2006-07-27 03:02:55 00:00:13 900K C++ glimpse

这道题就是个纸老虎，看上去复杂，真正做起来是很简单的。字符串分析+dfs（动态规划）都可以AC。

首先是对regular expression的分析。通过对题目的分析，我们不难发现，我们可以将regular expression分成n个block，这些block互相独立。一个block由两个部分组成。

1. 可以匹配的字符，ascii：0-255。遇到‘\’就从255个字符里删掉。

2. 匹配的格式。‘+’，‘*’和只需要匹配一次三种。

分别以matchde string的第1位到第i位为起点Dfs这n个block，记录下可以匹配的最长长度和位置。因为block之间无关系，match的时候可以用动态规划求解。

上述的代码200行就可以搞定。不过这题有两个trick：

1． regular expression可以为空，返回无法匹配

2． 可能出现i+*j的情况，一个字符后有n个表示次数的符号，忽略后面n-1个

上面的trick2不存在，经我assert，re格式还是很规范的。

trick1确实存在，不过其实更一般的，这里的正则不允许匹配一个空串，这与我们所熟悉的正则不同，题目和sample也没有说明，这是很不厚道的。

更不厚道的是，[T-F]并不是什么都不匹配，而是等价于[F-T]，描述用了暧昧的between，而sample完全消不了歧义。

最后，最恶心人的地方。这题有很容易引起麻烦的不在0~127范围的ASCII码。由于char是signed char还是unsigned char是没有标准的，通常正则里比较，总是认为那些编码大于127（从来没有人说编码小于0）的字符排序在后面。但这题就是与常识相背，得用signed char。

大家要引以为戒，如果暑期集训谁这么不厚道的做暧昧的描述（“能够自圆其说，但却处处是坑“，注意我们不是在做考研英语阅读理解），并且数据出得这么不厚道。那么先拿出去tjjtds三分钟，再bg全集训队吧。