Score : $400$ points

问题描述

给定由小写英文字母和?组成的字符串 $S$ 和 $T$。这里，满足 $|S| \gt |T|$（对于字符串 $X$，$|X|$ 表示 $X$ 的长度）。

若两个字符串 $X$ 和 $Y$ 满足 $|X|=|Y|$，则称它们 匹配 当且仅当：

• 可以通过独立地将 $X$ 和 $Y$ 中的每个 ? 替换为任意英文字母，使得 $X$ 等于 $Y$。

对于每个 $x=0,1,\ldots,|T|$ 解决以下问题：

• 让 $S'$ 为通过不改变顺序的方式，连接 $S$ 的前 $x$ 个字符和后 $(|T|-x)$ 个字符得到的长度为 $|T|$ 的字符串。如果 $S'$ 和 $T$ 匹配，则输出 Yes，否则输出 No。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given strings $S$ and $T$ consisting of lowercase English letters and ?. Here, $|S| \gt |T|$ holds (for a string $X$, $|X|$ denotes the length of $X$).

Two strings $X$ and $Y$ such that $|X|=|Y|$ is said to match if and only if:

• one can make $X$ equal $Y$ by replacing each ? in $X$ and $Y$ with any English letter independently.

Solve the following problem for each $x=0,1,\ldots,|T|$:

• Let $S'$ be the string of length $|T|$ obtained by concatenating the first $x$ characters and the last $(|T|-x)$ characters of $S$ without changing the order. Print Yes if $S'$ and $T$ match, and No otherwise.

Constraints

• $S$ and $T$ are strings consisting of lowercase English letters and ?.
• $1 \leq |T| \lt |S| \leq 3 \times 10^5$

Input

The input is given from Standard Input in the following format:

$S$

$T$

Output

Print $(|T|+1)$ lines.
The $i$-th line should contain the answer for $x=i-1$.

Sample Input 1

a?c
b?

Sample Output 1

Yes
No
No

When $x=0$, $S'$ equals ?c. Here, we can replace the $1$-st character of $S'$, ?, with b and the $2$-nd character of $T$, ?, with c to make $S'$ equal $T$, so $S'$ and $T$ match. Thus, Yes should be printed in the first line.
When $x=1$ and $2$, respectively, $S'$ is ac and a?, neither of which matches with $T$. Thus, No should be printed in the second and third lines.

Sample Input 2

atcoder
?????

Sample Output 2

Yes
Yes
Yes
Yes
Yes
Yes

Sample Input 3

beginner
contest

Sample Output 3

No
No
No
No
No
No
No
No

update @ 2024/3/10 12:00:03