题目背景

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。

5
80 /api/admin/**
60 /api/*/delete
75 /*/config/system
90 /api/users/*/password
50 /static/**/execute
8
/api/users/profile
/api/admin/users
/api/config/delete
/dev/config/system
/static/js/execute
/api/users/123/password
/static/css/js/execute
/api/admin

SAFE
ALERT: 80
ALERT: 60
ALERT: 75
ALERT: 50
ALERT: 90
ALERT: 50
ALERT: 80

提示

【样例说明】

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$。