解题思路

问题抽象

• 每个注册的 API 是一个以 / 开头、且不以 / 结尾的路径模式，由若干“段”组成（用 / 分隔）。
• 段要么是固定文本（如 api、user），要么是路径参数（形如 {id}，且整段都是参数）。
• 请求到来时，只有当段数一致且每个位置都满足：固定段完全相等，或该位置是参数段，才算匹配。
• 当多个 API 同时匹配时，参数尽量靠后的 API 优先（越靠前的位置越“具体”，固定段胜过参数段）。

题目内容

我们有一些提供 $HTTP$ 服务的 $Spring$ 应用，在 $HTTP$ 请求到达这些服务前，会先经过 $API$ 网关。网关需要根据 $HTTP$ 协议中的 $uri$ 信息将请求转发到对应的 $spring$ 应用服务。

$Spring$ 应用服务会在启动时扫描所有的 $@RequestMapping$ 注解，将它所提供的所有 $API$ 信息应用信息注册到 $API$ 网关。

由于 $@RequestMapping$ 的 $name$ 支持路径参数，所以 $HTTP$ 协议中的 $uri$ 和注册的 $API$ 不一定可以完全匹配。

比如 $API$ 可能是 $/api/user/${$userid$}，但请求的 $uri$ 是 $/api/user/123$ 。

现在，我们需要实现一个 $API$ 匹配算法，帮助 $API$ 网关找到这个 $HTTP$ 请求需要转发到哪个应用上。

假设 $API$ 一定以 $/$ 开头，且不会以 $/$ 结尾

路径参数一定是两个 $/$ 中的一整段，且被 { } 包围

除了路径参数的 { } ，其他地方不会出现 { }

$API$ 中更靠前的部分业务含义更明确，因此当出现两个 $API$ 都可被匹配时，路径参数出现在更靠后位置的 $API$ 应该被优先匹配，不同应用不会有相同的 $API$ ，但一个应用可能会有多个节点，一个 $api$ 可能被同应用的多个节点同时注册

输入描述

每一行代表一个操作。每行第一个信息表示动作

若动作为 $add$ ，则该行内容形如 $add,/api/playlist/${$playlistld$}$,playlist$。表示应用 $playlist$ 注册了一个路径为 $/api/playlist/${$playlistld$} 的 $API$

若动作为 $remove$ ，则该行内容形如 $remove,/api/playlist/${$playlistld$}$,playlist$。表示应用 $playlist$ 的某个节点下线了名为 $/api/playlist/${$playlistld$} 的 $api$

若动作为 $request$，则该行内容形如 $request,/api/playlist/123$ 。表示有一个 $uri$ 为 $/api/playlist/123$ 的请求到达网关，需要根据当前注册信息为其返回对应的应用名。$uri$ 字段不会包含 $?$ 以及 $?$ 后面的 $queryString$ 信息，也不会包含域名即域名之前的 $schema$ 信息

输出描述

针对每个 $request$ 动作，按顺序输出应用名，一个应用名一行，无匹配应用则输出 $null$

样例1

输入

add,/api/playlist/{playlistld},playlist
request,/api/user/get
request,/api/playlist/123/get
request,/api/playlist/123

输出

null
null
playlist