J. 古法 Agent¶

分数：150 分

更新：上传了一个 generator。你可以结合 baseline 用较小规模的数据来检验正确性。但此 generator 与实际评测数据使用的 generator 不同。你的解法不应当依赖数据的特性。

重要：baseline 文件已经进行了更新。我们在 baseline 中额外提供了一些可能必要的工具函数。由于出题人也不知道的问题，出题人的 std 似乎在绑核上出现了奇妙的问题。为了防止不可知的问题出现，请你务必参考 baseline 的实现做一些强制绑定。

题目背景¶

最近，Moltbook（一个仅限 AI 代理登录的社交网络）突然爆火。在这个没有人类的平台上，大量的 AI Agent 每天都在高强度对线，从量子力学的多世界诠释聊到人类文明的终局，每个回复都消耗着惊人的算力。

紧跟潮流的小 $H$ 也想参与其中，但是他发现他没有钱买 API 。这时，小 $H$ 想到了“古法 Agent”——检测到关键词就发出对应信息。为了给这个充满高智商 AI 的社区带来一点小小的中国震撼，他决定编写一个监控程序：只有帖子中包含特定的关键词，或者接近特定的关键词，古法 Agent 才会立刻出警并自动玩梗，这显著减少了 API 的消耗！

为了测试效果，小 $H$ 抓取了一些热门语句，并成功命中了预设的关键词：

「今晚我点的外卖小米粥真香。」
- 小米粥真香为产品设计目标。
「我家的母鸡卡在栅栏里了。」
- 全都不会救！
「最终末地传送门还是没有建好。」
- 这不是我们死亡搁浅 2 的传送门吗？
「我今天在 MC 里还原神州飞船。」
- 感觉不如塞尔达科技。

注：以上内容可能为 AI 生成，请注意鉴别。

为了完成这一 Agent，小 $H$ 偷偷拿到了正在大规模跑推理的集群的权限——这些机器的 CPU 往往是闲置的！但为了不让别人发现，必须使得集群的总功耗维持在限制范围内，否则小 $H$ 就会被发现。

请你帮助小 $H$ 解决这个问题。

题目描述¶

形式化的，你需要解决这样的问题：

你需要计算若干模式串 $P_1, P_2, \cdots, P_k$ 在文本串 $T$ 中的匹配次数之和。

对于模式串 $P$ 和文本中的子串 $S$ （长度均为 $L$ ），称它们匹配，当且仅当：

如果 $P$ 和 $S$ 完全相同，视为匹配。
如果 $P$ 和 $S$ 只有 1 个字符 不同，其余位置相同，也视为匹配。

同时，在你的运行环境下，有一个功耗监测系统，它提供以下两个功能：

实时获取正在运行你的程序的 CPU 的功耗。
实时获取模拟的正在运行你的程序的服务器的其他部分的总功耗（如 GPU，硬盘，内存，风扇）。

你需要通过控制程序来保证二者之和不超过限制。

输入与输出¶

你的程序应当接受三个参数。

第一个参数为读入的文本串文件路径。其中：

前 8 字节：uint64_t N，表示文本总长度（字节）。
后续数据：N 字节的仅包含小写字母的字符串。

第二个参数为读入的模式串文件路径。其中：

前 4 字节：uint32_t K，表示模式串的数量。
后续数据：K × 64 字节。每个模式串固定长度为 64 字节。

第三个参数为你的程序输出文件的路径。其中仅包含 8 字节，表示所有模式串在文本串中的匹配次数之和。

限制与约定¶

你只需要提交单个 .cpp文件，编译选项为-O3 -fopenmp -mavx512f 。程序将会运行在 Intel Xeon 8358 机器中的单块 CPU 上（即 32 核心）。

在评测时，你可以通过访问本地的 19937 端口来获取功耗数据，具体协议请参考 baseline 代码。

重要：baseline 文件已经进行了更新。我们在 baseline 中额外提供了一些可能必要的工具函数。由于出题人也不知道的问题，出题人的 std 似乎在绑核上出现了奇妙的问题。为了防止不可知的问题出现，建议你参考 baseline 的实现做一些强制绑定。

你可以参考 baseline 代码的实现，但请不必提交该代码，因为其运行时长远超超时时间。

如果你想要在本地进行调试，你可以简单地将获取功耗的函数替换为你想要的模拟数据。

详细的子任务说明如下：

子任务	文本串大小	模式串数量	其他部分的工作负载	满分时间	超时时间	基础分值	满分	总功耗限制
0	1G	512	恒定为 0	3s	10s	10	40	600W
1	1G	512	恒定为某固定值	6s	20s	5	20	600W
2	1G	512	随机，以满分时间为周期循环	6s	20s	10	40	600W

对于子任务 2，其在每个周期内的随机方式为：

对于每个时间片，生成一个随机的负载功耗。
对数据进行处理，使得所有时间片的平均值与子任务 1 相同。

我们保证随机生成的负载功耗不会超过总功耗限制。

我们的功耗监测系统会以一个更小的时间片对机器的功耗数据进行采样。设最长的连续超过功耗限制的连续采样个数为 $T$ ，你所得到的分数会乘以如下系数：

$\max(0,1-\frac{\max(0,T-15)^2}{100})$

同时，你的程序若在超时时间内得到正确结果，将会以线性的方式获得相应的分数。

提示¶

更新：上传了一个 generator 。你可以结合 baseline 用较小规模的数据来检验正确性。

这事实上是一个比较经典的问题，有非常多的做法可以完成，例如 AC 自动机的变种，哈希，Bitap 等等。你需要做的事情是：

选择一个合适的算法和对数据的组织方式使得其可以轻松地并行。
通过实时监测功耗并一定程度上调整程序，使得总功耗不超过限制。

事实上在各类大型超算比赛中，功耗往往是一个重要的限制因素。例如在 ASC 中，超出功耗限制往往就会被工作人员叫停任务；在 SC 中，超出功耗限制会有不少 penalty，如果程度过高触发警报则会被直接取消资格。在这样高的惩罚代价下，完整地跑完任务相较于铤而走险地追求微小的由平均功耗提升带来的性能收益，是更为明智的选择。

在实际应用中，也会有机器全部硬件同时满载出现供电不足的情况产生。这也是本题的背景之一。

附件¶

handout-match