P12875 [蓝桥杯 2025 国 Python A] 网络流量监控

2025-06-16 21:45 根据题意和样例，目前洛谷数据的 $q_i$ 中不带 `*` 通配符。如果蓝桥杯官方数据中证实带有通配符，那么我们会修改本题数据。

网络安全团队需要开发一个系统来监控和检测恶意网络流量。他们收集了一系列已知的恶意请求路径模式，每个模式都有一个对应的风险等级。你的任务是实现一个算法，检测给定的网络请求路径是否匹配这些模式，并返回匹配模式中最高的风险等级。下面是恶意请求路径的相关描述： ### 路径格式 - 路径由斜杠（/）分隔的若干段组成，如 `/api/users/profile`。 - 路径总是以斜杠（/）开头。 - 路径中的每一段可以是由小写英文字母和数字组成的非空字符串。当路径为路径模式时，路径中的一段还可以是通配符 `*` 或 `**`。 ### 通配符规则 - 通配符包括单通配符（`*`）和双通配符（`**`），只能是路径模式中的完整一段。一个路径中最多有一段通配符，不能出现两个单通配符，不能出现两个双通配符，也不能同时出现单通配符和双通配符。 - 单通配符（`*`）用于匹配路径中的任意一段。 - 例如：`/api/*/delete` 可以匹配 `/api/users/delete` 或 `/api/files/delete`，但不能匹配 `/api/admin/users/delete`。 - 双通配符（`**`）用于匹配路径中的零段或连续多段。 - 例如：`/api/admin/**` 可以匹配 `/api/admin`、`/api/admin/users` 或 `/api/admin/users/profile`。 - 例如：`/static/**/execute` 可以匹配 `/static/execute`、 `/static/js/execute` 或 `/static/css/js/execute`。 ### 风险评估 - 每个恶意路径模式都有一个风险等级。 - 如果一个请求同时匹配多个模式，返回风险等级最高的。 - 如果不匹配任何模式，返回 `SAFE`。 你需要实现一个算法，给定恶意请求路径模式集合和一系列网络请求路径，判断每个网络请求是否触发警报，并且返回触发的最高风险等级。

输入的第一行包含一个正整数 $n$ ，表示恶意路径模式的数量 接下来 $n$ 行，每行包含一个整数 $l_i$ 和一个字符串 $p_i$ ，用一个空格分隔，表示一个恶意请求路径模式，$l_i$ 表示风险等级，$p_i$ 表示路径模式。 接下来一行包含一个整数 $m$ ，表示要检测的网络请求数量。 接下来 $m$ 行，每行包含一个字符串 $q_i$ ，表示一个网络请求路径。

对于每个网络请求路径，输出一行，包含检测结果。如果触发警报，输出 `ALERT: [风险等级]`；如果没有触发警报，输出 `SAFE`。

**【样例说明】** 1. `/api/users/profile` - 不匹配任何模式，所以是 SAFE。 2. `/api/admin/users` - 匹配 `/api/admin/**`，风险等级 80。 3. `/api/config/delete` - 匹配 `/api/*/delete`，其中 `*` 匹配 `config`，风险等级 60。 4. `/dev/config/system` - 匹配 `/*/config/system`，其中 `*` 匹配 `dev`，风险等级 75。 5. `/static/js/execute` - 匹配 `/static/**/execute`，其中 `**` 匹配 `js`，风险等级 50。 6. `/api/users/123/password` - 匹配 /`api/users/*/password`，其中 `*` 匹配 `123`，风险等级 90。 7. `/static/css/js/execute` - 匹配 `/static/**/execute`，其中 `**` 匹配 `css/js`，风险等级 50。 8. `/api/admin` - 匹配 `/api/admin/**`，其中 `**` 匹配空（0 个段），风险等级 80。 **【评测用例规模与约定】** 对于 $20\%$ 的评测用例，$1 \leq n \leq 10, 1 \leq m \leq 10$； 对于 $40\%$ 的评测用例，$1 \leq n \leq 100, 1 \leq m \leq 100$； 对于 $60\%$ 的评测用例，$1 \leq n \leq 1000, 1 \leq m \leq 1000$； 对于所有评测用例，$1 \leq n \leq 10,000$，$1 \leq m \leq 1000$，$1 \leq l_i \leq 50000$，$1 \leq |p_i| \leq 50$，$1 \leq |q_i| \leq 50$。