#2365. 四个问号的子串匹配

四个问号的子串匹配

题目背景

卡卡在玩一个字符串游戏,他得到了一个包含“?”占位符的神秘字符串 TT,与此同时,他想知道某个目标字符串 UU 是否可能是原始字符串的子串。

题目描述

给定一个字符串 TT,它由小写英文字母和 '?' 组成;以及一个只包含小写英文字母的字符串 UU。字符串 TT 是从某个仅包含小写字母的原始字符串 SS 中,通过将恰好四个字符替换为 '?' 而得到的。判断是否存在一种对 '?' 的替换方式,使得原始字符串 SS 中包含 UU 作为连续子串。

输入格式

第一行:字符串 TT,长度满足 4T104 \le |T| \le 10,由小写字母和 '?' 组成,且恰好包含四个 '?'。
第二行:字符串 UU,长度满足 1UT1 \le |U| \le |T|,由小写字母组成。

输出格式

如果存在一种替换方式使得原始字符串 SS 包含 UU 作为连续子串,输出 Yes;否则输出 No。

样例

tak??a?h?
nashi
Yes

样例解释

在样例 1 中,如果原始字符串 SS 为 "takanashi",那么 SS 包含 "nashi" 作为连续子串,所以答案是 Yes。

??e??e
snuke
No

在样例 2 中,无论如何替换 '?' ,都无法在 SS 中得到 "snuke" 作为连续子串。

????
aoki
Yes

在样例 3 中,可以将所有 '?' 替换为 "aoki",直接匹配。

数据范围

  • 4T104 \le |T| \le 10,且 TT 恰好包含四个 '?'。
  • 1UT1 \le |U| \le |T|

abc403_b-Four Hidden