#P14195. [清华集训 2014] Router
[清华集训 2014] Router
Router:路由匹配与简化正则表达式
题目描述
在 Web 后端开发中,**路由器(Router)**负责根据请求 URL,找到与之对应的处理程序(Action)。
请求 URL 的形式为:
/segment1/segment2/.../segmentk
/segment1/segment2/.../segmentk?name1=value1&name2=value2&...&namen=valuen
其中 ? 后面的部分称为查询参数列表。匹配路由时,只考虑 ? 前面的路径;查询参数直接传递给匹配到的 Action。
例如:
/user/list/show?gender=male&birthyear=1990
其路径为 /user/list/show,查询参数分别为 gender=male、birthyear=1990。
1. 路由规则
每条路由规则(Path)由若干个用 / 分隔的段组成,例如:
/user/list/show
/user/:handle/show
一段可以是具体的字符串,也可以是 : 加一个正则表达式名称。假设 handle 对应的正则表达式能够匹配非空的小写字母串,那么:
/user/testuser/show?avatar=true&message=hello
能够匹配 /user/:handle/show。执行对应 Action 时,还要传递路径参数 handle=testuser,以及两个查询参数 avatar=true、message=hello。
每一个正则表达式必须匹配完整的一段路径,而不是仅匹配该段的某个子串。
2. 路由之间的限制
设两条不同的 Path 的前 段完全相同(如果某段使用正则表达式,则要求正则表达式名称相同),且它们的第 段不同。数据保证:
- 如果一条 Path 的该段为普通字符串,另一条为正则表达式,那么该正则表达式无法匹配前者的普通字符串。
- 如果两条 Path 的该段都是不同的正则表达式,则这两个正则表达式能够匹配的字符串没有交集。
数据还保证同一个请求不会被多条 Path 匹配。
3. 简化正则表达式文法
本题使用的正则表达式由下列规则组成:
Regexp(正则表达式)
- 一个
Alternative;或 Alternative|Regexp,表示两者的或。
Alternative(连接分支)
由一个或多个 Term 直接连接而成,表示依次匹配各个 Term。
Term(带重复次数的项)
- 一个
Atom;或 Atom后接一个Quantifier。
Quantifier(重复次数)
格式为 {lower_bound,upper_bound},其中 ;也允许写成 {lower_bound,},表示重复次数没有上界。下界与存在时的上界均为不超过 的非负整数。
例如:{1,3}、{0,1}、{2,2}、{3,} 均合法,而 {3,2}、{,1} 不合法。
**Atom(原子)**有三种形式:
- 单个英文字母或数字,匹配该字符;
- 字符区间
[lower-upper],两个端点必须同为小写字母、同为大写字母或同为数字,且lower的 ASCII 码不大于upper,匹配区间内的任意一个字符; (Regexp),匹配括号内的正则表达式。
例如:
[0-9]{1,3}:由 1~3 个数字组成的字符串;([a-z]|[0-9]){3,10}:由 3~10 个小写字母或数字组成的字符串;01[0-1]{0,}|10[0-1]{0,}:以01或10开头、后面接任意长度二进制串的字符串。
输入格式
第一行是正整数 ,表示测试组数。对每组测试:
- 第一行是正整数 ,表示 Path 的数量。
- 接下来的 行,每两行描述一个 Path:第一行是路径,第二行是它对应的 Action 名称。
- 随后若干行是所有不同正则表达式名称的定义。每行包含两个非空字符串
regexp_name regexp,用一个空格隔开。每个曾在 Path 中出现的名称恰好定义一次,不存在未使用的定义。这一部分没有单独的数量行。 - 下一行是正整数 ,表示请求数量。
- 接下来的 行,每行一个请求 URL。
各字段限制:
- 普通 Path 段由大小写英文字母与数字组成,长度为 。
- 正则表达式名称只由大小写英文字母组成,长度为 。
- Action 名称只由大小写英文字母组成,长度为 。
- 每个正则表达式长度不超过 。
- 请求路径段、查询参数的值由大小写英文字母和数字组成,长度为 。
- 查询参数的名称由大小写英文字母组成,长度为 。
输出格式
对第 组数据,先输出:
Case #t:
随后按输入顺序,对每个请求输出一行:
- 若没有匹配的 Path,输出
404 Not Found。 - 否则输出:
Request matches action "action_name" with parameters {parameter_list}
parameter_list 使用类似 JSON 的字典格式,按参数名称的字典序升序排列:
- 某个参数名称只出现一次时,输出
"name":"value"。 - 同名参数出现多次时,输出
"name":["value1","value2",...],并保持参数出现的先后顺序:先按 Path 中从左到右的匹配段,后按 URL 查询列表从左到右。 - 无参数时输出
{}。
注意:即使请求未匹配,仍然只输出一行 404 Not Found。
输入输出样例 #1
输入 #1
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
输出 #1
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"}
数据范围
- ;
- (每组测试);
- 不同正则表达式名称最多 个;
- 每个输入文件大小不超过 10 MB;
- 对于 的数据,Path 中不出现正则表达式。