Problem B. 词典
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Description
小 W 是一名 c++ 语言的初学者,他实在是受不了了! 他不记得算法库是 algorithm 还是 algoritm。他不记得写头文件用 include 还是 inclube。他不记得 排列是 permutation 还是 permiutation。 为了解决这个问题,小 W 请你写一个词典来解决这个问题。这样当他有疑问的时候就可以用这个词 典了。 具体来说,小 W 首先会给你 n 个单词,接着 q 次询问,每次询问给你一个单词,你需要告诉小 W 词典中与这个单词编辑距离不超过 1 的单词是什么。如果不存在这样的单词,请输出 No,保证答案唯一。 如果你不知道编辑距离的定义,你只需要知道若字符串 s 与字符串 t 的编辑距离不超过 1 说明,s 与 t 相等,或者 s 是 t 在删去一个字符的结果,或者 s 是 t 在一个位置加上一个字符的结果,或者 s 是 将 t 中的一个字符修改为另一个的结果。第二段的例子恰好对应了后三种情况。
Format
Input
第一行两个整数 n, q,含义见题目描述。 接下来 n 行,每行一个字符串表示词典中初始的单词。 接下来 q 行,每行一个字符串表示小 W 这次询问的单词。 保证这些单词由小写字母组成。
Output
共 q 行,每行一个词典中的单词,是词典中与询问单词编辑距离不超过 1 的单词。如果不存在这样的单词,则为 No。
Samples
5 5
input
output
example
cjiajia
dict
nput
inpuxt
input
dicti
ditc
input
input
input
dict
No
Limitation
对于 60% 的数据,满足词典中要么只有与询问完全相同的单词,要么答案为 No。 对于全部数据,满足 n ≤ 50, q ≤ 50,字符串长度 ≤ 20。