#P14195. [清华集训 2014] Router

    ID: 13403 传统题 2000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>字符串数据结构图论CF2400模拟搜索字典树

[清华集训 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 的前 ii 段完全相同(如果某段使用正则表达式,则要求正则表达式名称相同),且它们的第 i+1i+1 段不同。数据保证:

  • 如果一条 Path 的该段为普通字符串,另一条为正则表达式,那么该正则表达式无法匹配前者的普通字符串。
  • 如果两条 Path 的该段都是不同的正则表达式,则这两个正则表达式能够匹配的字符串没有交集。

数据还保证同一个请求不会被多条 Path 匹配。

3. 简化正则表达式文法

本题使用的正则表达式由下列规则组成:

Regexp(正则表达式)

  • 一个 Alternative;或
  • Alternative|Regexp,表示两者的或。

Alternative(连接分支)

由一个或多个 Term 直接连接而成,表示依次匹配各个 Term。

Term(带重复次数的项)

  • 一个 Atom;或
  • Atom 后接一个 Quantifier。

Quantifier(重复次数)

格式为 {lower_bound,upper_bound},其中 0≤lower_bound≤upper_bound≤200\le lower\_bound\le upper\_bound\le20;也允许写成 {lower_bound,},表示重复次数没有上界。下界与存在时的上界均为不超过 2020 的非负整数。

例如:{1,3}、{0,1}、{2,2}、{3,} 均合法,而 {3,2}、{,1} 不合法。

**Atom(原子)**有三种形式:

  1. 单个英文字母或数字,匹配该字符;
  2. 字符区间 [lower-upper],两个端点必须同为小写字母、同为大写字母或同为数字,且 lower 的 ASCII 码不大于 upper,匹配区间内的任意一个字符;
  3. (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 开头、后面接任意长度二进制串的字符串。

输入格式

第一行是正整数 TT,表示测试组数。对每组测试:

  1. 第一行是正整数 NN,表示 Path 的数量。
  2. 接下来的 2N2N 行,每两行描述一个 Path:第一行是路径,第二行是它对应的 Action 名称。
  3. 随后若干行是所有不同正则表达式名称的定义。每行包含两个非空字符串 regexp_name regexp,用一个空格隔开。每个曾在 Path 中出现的名称恰好定义一次,不存在未使用的定义。这一部分没有单独的数量行。
  4. 下一行是正整数 MM,表示请求数量。
  5. 接下来的 MM 行,每行一个请求 URL。

各字段限制:

  • 普通 Path 段由大小写英文字母与数字组成,长度为 1∼501\sim50。
  • 正则表达式名称只由大小写英文字母组成,长度为 1∼301\sim30。
  • Action 名称只由大小写英文字母组成,长度为 1∼301\sim30。
  • 每个正则表达式长度不超过 5050。
  • 请求路径段、查询参数的值由大小写英文字母和数字组成,长度为 1∼501\sim50。
  • 查询参数的名称由大小写英文字母组成,长度为 1∼301\sim30。

输出格式

对第 tt 组数据,先输出:

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"}

数据范围

  • 1≤T≤51\le T\le5;
  • 1≤N,M≤200001\le N,M\le20000(每组测试);
  • 不同正则表达式名称最多 5050 个;
  • 每个输入文件大小不超过 10 MB;
  • 对于 30%30\% 的数据,Path 中不出现正则表达式。