问题 B - Four Hidden (难度：中等) 竞技编程-提高思维

题目描述

给定一个由小写字母和 ? 组成的字符串 T，以及一个由小写字母组成的字符串 U。

字符串 T 是通过取某个只包含小写字母的字符串 S，并将其中的四个字符替换为 ? 得到的。

请判断原始字符串 S 是否可能包含 U 作为一个连续子串。

输入格式

输入的格式如下：

T
U

• T 的长度在 4 到 10 之间，且由小写字母和 ? 组成。
• T 中恰好有四个 ?。
• U 的长度在 1 到 |T| 之间，且由小写字母组成。

输出格式

输出一个字符串：如果原始字符串 S 可能包含 U 作为一个连续子串，输出 "Yes"；否则输出 "No"。

样例输入 1

tak??a?h?
nashi

样例输出 1

Yes

解释：例如，如果 S 是 "takanashi"，它包含 "nashi" 作为一个连续子串。

样例输入 2

??e??e
snuke

样例输出 2

No

解释：无论如何替换 T 中的 ?，S 都无法包含 "snuke" 作为一个连续子串。

样例输入 3

????
aoki

样例输出 3

Yes

时间复杂度分析

本题的时间复杂度为 O(n)O(n)，其中 nn 是字符串 TT 的长度。我们需要遍历 TT 中的每个字符并进行比对，处理的字符数不超过 10，因此时间复杂度是可以接受的。