机械字典匹配(Watto and Mechanism)

题目描述

Watto 是一家零件商店的老板，他最近接到一个订单，需要一种可以以特定方式处理字符串的机制。最初，该机制的存储器中存储有 $n$ 个字符串。之后，该机制需要能够处理如下类型的查询：“给定字符串 $s$，判断机制的存储器中是否存在某个字符串 $t$，它与 $s$ 长度相同，并且与 $s$ 恰好只在一个位置上不同。”

Watto 已经组装好了这个机制，现在只需为其编写程序，并用包含 $n$ 条初始字符串和 $m$ 条查询的数据进行测试。他决定将这项任务交给你。

输入格式

第一行包含两个非负整数 $n$ 和 $m$（$0 \leq n \leq 3 \cdot 10^{5}$，$0 \leq m \leq 3 \cdot 10^{5}$），分别表示初始字符串的数量和查询的数量。

接下来有 $n$ 行，每行是一个非空字符串，表示要上传到机制存储器中的字符串。

接下来有 $m$ 行，每行是一个非空字符串，表示对机制的每次查询。

输入中的所有字符串总长度不超过 $6 \cdot 10^{5}$。每个字符串仅由字母 'a'、'b'、'c' 组成。

输出格式

对于每个查询，如果存储器中存在所需的字符串，则输出一行 “YES”；否则，输出一行 “NO”。

样例输入 #1

2 3
aaaaa
acacaca
aabaa
ccacacc
caaac

样例输出 #1

YES
NO
NO

数据范围

由 ChatGPT 5 翻译

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1800。

测试点分布

出处：原题链接