D. 我是拼写大王

题目描述

定义：

• 若字符串 $s$，$t$ 满足 $s=t$，则称它们内容完全一致。
• 若字符串 $s,t$ 满足以下条件之一，则称它们 内容相似 。
  • 在 $s$ 中任意位置添加一个字符，可以得到 $t$。
  • 在 $s$ 中任意位置删去一个字符，可以得到 $t$。
  • 在 $s$ 中任意位置改变一个字符，可以得到 $t$。

现给定字典 $D$ 和待检查的字符串 $s$(s 中包含由空格组成的若干单词)，请设计一个拼写检查程序，对于 $s$ 输出修改建议。具体来说：

• 对于 $s$ 中的某个单词，如果字典中存在该单词，则拼写无误，不需要修改。
• 否则（字典中不存在该单词的情况），如果字典中存在 唯一 的 内容相似 的单词，请将该单词修改为该单词，作为修改建议。
• 对于其他情况，在该单词末尾添加一个问号'?'，表示此处需要手动检查单词的拼写是否有误。

例如，$D=\{this,is,a,bat, that, cat, b, c\},s=thus\ was \ a\ hat$，则：

• 第一个单词无法在字典中找到，但有唯一修改方案 this
• 第二个单词无法在字典中找到，但是字典中没有相似单词，所以直接插入一个 '?'
• 第三个单词正确，能找到原单词。所以不考虑两个相似的单词 b 和 c。
• 第四个单词无法在字典中找到，但是有两种修改方案 bat 和 cat，所以直接插入一个 '?'

因此，修改建议为：$'this \ was? \ a \ hat?'$，注意字符串原来的空格保持不变。

输入格式

第一行一个正整数 $n$，表示字典的单词数。

接下来一行 $n$ 个单词 $d_i$ 用单个空格隔开，表示字典中的单词。

第三行仅一个字符串 $s$，表示待分析的字符串。

输出格式

一个字符串，表示修改意见。

遇到字典中存在的单词时，原样输出。

否则，遇到字典中唯一相似的单词时，修改为该单词。

否则，在该单词末尾添加问号 ?。

样例输入1

8
this is a bat that cat b c
thus was a hat

样例输出1

this was? a hat?

样例输入2

4
a ab abc c
abcd acbd adbc bc

样例输出2

abc acbd? abc bc?

数据范围及约定

对于 $60\%$ 的数据，$n=1$，$s$ 不含空格。$1\le |s|, |\sum d_i| \le 10$。

对于 $100\%$ 的数据，$1\le n\le 500, |d_i|\neq 0,1\le |\sum d_i|\le 5000, 1\le |s|\le 5000$。

字典中各单词 $d_i$ 仅由小写字母组成，且 $1\le i,j\le n$ 时 $i\neq j \leftrightarrow d_i\neq d_j$。

$s$ 仅由小写字母和空格组成，$s$ 的开头和结尾不含空格，且 $s$ 中任意两个单词之间一定用一个空格隔开。