-
题目分类：general
-
题目分值：150
小 F 是一位狂热的正则表达式爱好者。今天，他写了一个在线的正则验证服务：服务器会运行你的正则，返回匹配结果。
小 F 还说，如果有人能卡住服务器（运行时间超过 1 秒），他就会送出自己的 flag。
当然，为了避免太容易拿到 flag，小 F 限制了正则和字符串的长度，具体内容请查看源代码。
你可以通过 nc 202.38.93.241 10006 命令来连接题目，或者使用我们提供的网页终端。
如果你不知道 nc 是什么，或者在使用上面的命令时遇到了困难，可以参考我们编写的 萌新入门手册：如何使用 nc/ncat？
正则表达式在各种软件开发中是很常用的工具，但是稍微不注意的话就会导致代码出现 DoS 的漏洞，即精心挑选的正则表达式（或者待匹配字符串）可以让匹配引擎长时间运行，占用大量 CPU 资源，这道题就是考这个小知识的。
找到一个能卡住匹配引擎的表达式并不难，例如 Wikipedia 上的第一个示例就可以直接拿来用：
Regex: (a*)*$
String: aaaaaaaaaaaaaaaaaaaaaaab
上面这个正则由于失败时回溯的存在，每增加一个 a 就会使匹配时间翻一倍，出题时我测算了几次，i7-8850H (4.30 GHz) 可以在 1 秒内对 25 个 a 运行（并失败），所以实际字符串限制我就写成了 24 个字符。