#P11718. [清华集训 2014] Router
[清华集训 2014] Router
题目描述
在进行 Web 后端开发时,很重要的一个组件是 router。通常来说,后端的代码由许多 action 组成,router 的作用就是将发来的请求按照 URL 对应到相应的 action 上。
请求到达后端 Web 服务器时,已经不需要考虑域名和端口了,因此一个请求有如下形式:
<samp>/{something_1}/{something_2}/.../{something_k}</samp>
或 <samp>/{something_1}/{something_2}/.../{something_k}?{parameter_list}</samp>
其中 parameter_list 的组成为:<samp>{name_1}={value_1}&{name_2}={value_2}&...&{name_n}={value_n}</samp>
。(第一种情况中的 parameter_list
为空)
例如 <samp>/user/list/show?gender=male&birthyear=1990</samp>
就是一个合法的请求,其中包含了两个参数 gender 和 birthyear,对应的 value 分别是 male 和 1990。
router 由许多条 path 组成,每一个 path 会对应到一个 action 上。router 在匹配 URL 到 path 时只看 parameter_list 之前的部分,例如之前的请求就只看 <samp>/user/list/show</samp>
这部分。parameter_list 内的参数会被直接送到 action 中。因此一个 path 总是具有如下形式:
<samp>/{something_1}/{something_2}/.../{something_k}</samp>
为了使得 router 更灵活,每一段中的 something 除了可以用具体的字符串外,还可以用一个正则表达式去匹配,并且提取出这部分的内容作为参数送到 action 去。这种情况下,something 的内容为 <samp>:{regexp_name}</samp>
,其中 regexp_name 对应一个正则表达式,会在后面给出具体的表达式。例如 router 中的一个 path 为 <samp>/user/:handle/show</samp>
,其中<samp>:handle</samp>
对应了一个正则表达式,假设它可以匹配所有由小写英文字母组成的非空串。此时请求 <samp>/user/testuser/show</samp>
就能匹配这个 path,并且送往 action 多了一个 name 为 handle、value 为 testuser 的参数。再例如请求为 <samp>/user/testuser/show?avatar=true&message=hello</samp>
的话,不仅能匹配之前的 path,送到 action 的参数就会有三个:handle、avatar、message,对应的 value 分别为 testuser、true 和 hello。
但是使用带正则表达式的 path 时也受到一些限制。具体来说,如果有 router 中有两个 path,他们前面 个 something 段的内容完全相同(这 段里面可以含正则表达式项,此时就要求是名称相同的正则表达式),然后第 个 something 段的内容不同。下面分两种情况:
- 一个 path 这一段的内容是普通字符串,另一个 path 这一段的内容对应了正则表达式,那么这个正则表达式一定无法匹配前一个 path 第 段的字符串。例如一个 path 是
<samp>/foo/:tmp/bar/pop</samp>
,另一个 path 是<samp>/foo/:tmp/:exp/push</samp>
,那么 exp 对应的正则表达式一定不会匹配 bar。 - 两个 path 这一段的内容都是正则表达式,那么这两个正则表达式匹配的字符串一定没有交集。例如一个 path 是
<samp>/foo/:tmp/:aaa/push</samp>
,另一个 path 是<samp>/foo/:tmp/:bbb/pop</samp>
,那么不存在一个字符串能同时被 aaa 对应的正则表达式和 bbb 对应的正则表达式匹配。
最后介绍正则表达式。为了让情况简单一些,本题中的正则表达式规则相比于实际使用的有所简化。正则表达式的文法中有 Atom、Quantifier、Term、Alternative 这几个概念。用 Regexp 表示正则表达式,则每种概念具体为:
- Regexp 可以由单个 Alternative 组成,或者由一个 Alternative 和一个 Regexp 组成,中间用字符
<samp>|</samp>
连接。对于前一种情况,该正则表达式匹配所有 Alternative 能匹配的东西。对于后一种情况,一个字符串要能被该正则表达式匹配,要么能被<samp>|</samp>
前面的 Alternative 能匹配,要么能被<samp>|</samp>
后面的 Regexp 所匹配。 - Alternative 由单个 Term 或多个 Term 连接组成,它能匹配这些 Term 所匹配的字符串的连接。换言之,一个字符串要被这个 Alternative 匹配,这个字符串能够拆成若干段(段数和 Alternative 的 Term 个数一样多),每段依次被 Alternative 的每个 Term 匹配。
- Term 由一个 Atom 或一个 Atom 附带一个 Quantifier 组成。后面会了解到,Quantifier 对应了允许重复次数的区间。若 Term 由单个 Atom 组成,则 Term 能匹配的内容与 Atom 相同。如果 Atom 后带了 Quantifier,则如果一个字符串能划分为若干段(划分的段数在 Quantifier 指定的区间内),使得每段都能被 Atom 匹配,那么这个字符串就能被这个 Term 匹配。
- Quantifier 的形式为
<samp>{lower_bound,upper_bound}</samp>
,其中 lower_bound 和 upper_bound 各对应一个不超过 的非负整数,并且 ,Quantifier 对应的区间为闭区间 。注意 upper_bound 可以为空(此时中间的逗号还是有的),upper_bound 为空表示上界为无穷大。<samp>{1,3}</samp>
,<samp>{0,1}</samp>
,<samp>{2,2}</samp>
,<samp>{3,}</samp>
均为合法的 Quantifier,但<samp>{3,2}</samp>
,<samp>{,1}</samp>
就不合法。 - Atom 有三种形式:第一种为单个字符,这里字符约定只能是英文字符(包括大写和小写)和数字,这种形式下的 Atom 所能匹配的内容就是该字符。第二种形式为字符区间,具体形式为
<samp>[lower-upper]</samp>
,这里 lower 和 upper 各为单个字符,满足要么同时为小写英文字母、要么同时为大写字母、要么同时为数字,并且 lower 的ASCII码不小于 upper 的ASCII码,这种情况下的 Atom 所能匹配的内容就是这个区间内的字符(包括 lower 和 upper)。第三种形式是<samp>(Regexp)</samp>
,即一个合法的正则表达式套上一对括号,这种情况下该 Atom 能匹配的内容和括号内的正则表达式相同。
根据以上文法,<samp>[0-9]{1,3}</samp>
为合法的正则表达式,它能匹配长度为 且由数字组成的字符串。<samp>([a-z]|[0-9]){3,10}</samp>
也为合法的正则表达式,它能匹配长度为 且由小写英文字母和数字组成的字符串。更复杂的一个例子为 <samp>01[0-1]{0,}|10[0-1]{0,}</samp>
,它能匹配所有 <samp>01</samp>
或 <samp>10</samp>
开头的 <samp>01</samp>
字符串。
输入格式
第一个一个正整数 ,表示数据的组数。下面依次给出每组数据。
每组数据的第一行包含一个正整数 ,表示 router 中有 个 path。下面 行,每两行描述一个 path,第一行为 path 匹配的 URL,形式为
<samp>/{something_1}/{something_2}/.../{something_k}</samp>
每段 something 要么为具体的字符串(由大写英文字母、小写英文字母和数字组成且长度在 内),要么为 <samp>:{regexp_name}</samp>
,其中 regexp_name 由大写和小写英文字母组成且长度不超过 。具体的正则表达式会在之后的输入中给出。描述该 path 的第二行为对应的 action 名称(由大写和小写英文字母组成,长度在 内)。
下面若干行描述前面 path 中出现的所有正则表达式,每行描述一个正则表达式,每行内包含两个非空字符串(由一个空格隔开),前面的字符串表示 regexp_name,后面的字符串表示对应正则表达式(长度不超过 )。注意同一个 regexp_name 可能在前面给出的 path 中出现多次(一个 path 中出现多次或在不同 path 中出现),这种情况下他们对应的正则表达式是相同的,并且输入中只会描述一次。数据同时保证这里给出的 regexp_name 都至少在一个 path 中出现过。
下面一行包含一个正整数 ,表示有 个请求发了过来。下面 行,每行描述一个请求的 URL。URL 为 <samp>/{something_1}/{something_2}/.../{something_k}</samp>
或 <samp>/{something_1}/{something_2}/.../{something_k}?{name_1}={value_1}&{name_2}={value_2}&...&{name_n}={value_n}</samp>
的形式,其中所有 something 和 value 都由大写英文字母、小写英文字母和数字组成且长度在 内,所有 name 都由大写和小写英文字母组成且长度在 内。
输出格式
对于每组数据,先单独一行输出 <samp>Case #{case_no}:</samp>
(不含引号),其中 case_no 表示当前是第几组数据(从 开始编号)。
每行输出依次对应每个请求。如果没有 path 能够匹配该请求的 URL,输出 <samp>404 Not Found</samp>
。
如果有 path 能够匹配改请求,输出 <samp>Request matches action "{action_name}" with parameters {parameter_list}</samp>
,其中 action_name 为匹配 path 对应 action 的名称,parameter_list 为所有的参数。
- 其中 parameter_list 用一个字典的方式输出。例如有三个参数,他们的 name 为 avatar、message 和 page,对应的 value 分别为 true、hello 和 2,那么输出的 parameter_list 为
<samp>{"avatar":"true","message":"hello","page":"2"}</samp>
(所有参数按照 name 的字典序排列)。 - 注意一个请求中,拥有相同 name 的参数可能出现多次,例如请求的 URL 为
<samp>/user/me/show?name=you&name=he</samp>”,匹配的 path 为 “<samp>/user/:name/show</samp>
,此时的 parameter_list 为<samp>{"name":["me","you","he"]}</samp>
。方括号里面按照参数在请求 URL 中出现的次序给出。 - 更多具体的例子请参考样例。数据能够保证一个请求不会被多个 path 匹配。
3
3
/user/:id/show
userShow
/message/list
messageList
/message/:id/show
messageShow
id [0-9]{2,4}
3
/message/list
/user/123/show?avatar=true
/message/5312/show?page=1
1
/foo/:id/:bar/:bar
fun
id [0-9]{2,4}
bar [a-z]{1,3}
1
/foo/777/az/bc?bar=xyz&bar=zzz
2
/user/:handle/show
userShow
/user/:id/show
userShow
id [0-9]{2,4}
handle ([a-z]|[A-Z])([a-z]|[A-Z]|[0-9]){4,10}
4
/user/259/show
/user/wjmzbmr/show?like=true
/user/0xxx/show
/user/WJMZBMR/show?love=true
Case #1:
Request matches action "messageList" with parameters {}
Request matches action "userShow" with parameters {"avatar":"true","id":"123"}
Request matches action "messageShow" with parameters {"id":"5312","page":"1"}
Case #2:
Request matches action "fun" with parameters {"bar":["az","bc","xyz","zzz"],"id":"777"}
Case #3:
Request matches action "userShow" with parameters {"id":"259"}
Request matches action "userShow" with parameters {"handle":"wjmzbmr","like":"true"}
404 Not Found
Request matches action "userShow" with parameters {"handle":"WJMZBMR","love":"true"}
提示
对于 30% 的数据,path 中不会出现正则表达式;
对于 100% 的数据,,,输入文件大小不超过 。不同名称的正则表达式最多有 个。
注意此题数据是良心数据。