3378 - 电子字典

人们在英文字典中查找某个单词的时候可能不知道该单词的完整拼法，而只知道该 单词的一个错误的近似拼法，这时人们可能陷入困境，为了查找一个单词而浪费大 量的时间。带有模糊查询功能的电子字典能够从一定程度上解决这一问题：用户只 要输入一个字符串，电子字典就返回与该单词编辑距离最小的几个单词供用户选择。
字符串a与字符串b的编辑距离是指：允许对 a 或 b 串进行下列“编辑”操作，将 a 变为 b 或 b 变为 a，最少“编辑”次数即为距离。

1. 删除串中某个位置的字母；
   
2. 添加一个字母到串中某个位置；
   
3. 替换串中某一位置的一个字母为另一个字母。
   小兰团队正在开发一款电子字典，你需要帮助团队实现一个用于模糊查询功能的计 数部件：对于一个待查询字符串，如果它是单词，则返回 −1；如果它不是单词， 则返回字典中有多少个单词与它的编辑距离为 1。
   

第一行包含两个正整数 N 和 M。
接下来的 N 行，每行一个字符串，第 i + 1 行为单词 Wi，单词长度在 1 至 20 之 间。
再接下来 M 行，每行一个字符串，第 i + N + 1 表示一个待查字符串 Qi。待查 字符串长度在 1 至 20 之间。 Wi 和 Qi 均由小写字母构成，文件中不包含多余空格。

输出应包括M行，第i行为一个整数Xi：
Xi = − 1 表示 Qi为字典中的单词；
否则 Xi 表示与 Qi编辑距离为1的单词的个数。

【样例1解释】
abcd 在单词表中出现过；
abc与单词 abcd、 aabc的编辑距离都是 1；
abcdd与单词 abcd 、abcde、abced的编辑距离都是 1。
【数据范围】
所有单词互不相同，但是查询字符串可能有重复；
· 对 50% 的数据范围，N, M ≤ 10^3；
· 对 100% 的数据范围，N, M ≤ 10^4。

NOIP