分数: 233 分
问题陈述
高桥和青木在同一堂课上分别做了笔记。不过,两人都有看不懂的部分,所以他们的笔记上都有一些空白。
听课时黑板上写的内容是一串 N 仅由小写英文字母组成的字符。让字符串 S 代表高桥的音符和字符串 T 代表青木的笔记。两者都 S 和 T 包括 N 字符,其中无法读取的部分记录为 ?。其他部分均记录为小写英文字母,但由于抄写错误,部分字符可能与原黑板内容有所不同。
两人互相比较笔记并尝试重建原始的黑板内容。他们决定相信他们俩写下的相同字符。对于每个位置 i (1 \leq i \leq N),他们比较 i- 第一个字符 S 与 i- 第一个字符 T 并确定 i第一个字符按照以下规则重建:
- 如果两者是相同的小写英文字母,则采用该字母。
- 如果是
?另一个是小写英文字母,采用该小写英文字母。 - 如果两者都是
?,该字符无法重建,因此它仍然存在?. - 如果两者都是小写英文字母但彼此不同,则至少有一个注释存在复制错误,无法确定正确的字符,因此变为
!代表矛盾。
对所有位置执行重构后输出结果字符串。另外,判断重构结果是否包含至少一个矛盾(!),并输出 Yes 如果是这样,或者 No 如果没有。
约束
- 1 \leq N \leq 5 \times 10^5
- N 是一个整数。
- S 是一个长度为的字符串 N 由小写英文字母和
?. - T 是一个长度为的字符串 N 由小写英文字母和
?.
输入
N S T
- 第一行包含一个整数 N 表示字符串的长度。
- 第二行包含字符串 S 长度 N 代表高桥的笔记。
- 第三行包含字符串 T 长度 N 代表青木的笔记。
输出
输出输入 2 行。
- 第一行,输出重建后的字符串长度 N。每个位置的字符是根据问题陈述中描述的规则确定的。
- 第二行,输出
Yes如果重建结果至少包含一个!(即存在矛盾),或No否则。
示例输入 1
5 ab?de a?cd?
示例输出 1
abcde No
示例输入 2
6 abc?ef axc?yf
示例输出 2
a!c?!f Yes
示例输入 3
15 he??o?wor?d?abc ?ell??world?axc
示例输出 3
hello?world?a!c Yes
示例输入 4
40 ab?dab?dab?dab?dab?dab?dab?dab?dab?dab?d a?cda?cda?cda?cda?cda?cda?cda?cda?cda?cd
示例输出 4
abcdabcdabcdabcdabcdabcdabcdabcdabcdabcd No
示例输入 5
1 ? ?
示例输出 5
? No