102873: [AtCoder]ABC287 D - Match or Not

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:1 Solved:0

Description

Score : $400$ points

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

Input

题意翻译

给定两个字符串 $S$ 和 $T$(其中 $|S|$ 表示字符串 $S$ 的长度),对于 $x=0,1,...,|T|$ 依次求解如下问题: 令 $U$ 为 $S$ 的前 $x$ 个字符与最后 $|T|-x$ 个字符组成的字符串,是否存在一种方式使得将 $T$ 和 $U$ 中的每一个 `?` 替换成任意的小写字母使得 $T=U$?如果存在,输出 `Yes`,否则输出 `No`。 数据范围: 对于 $100\%$ 的数据:$1\leq |T|<|S|\leq 3\times 10^5$,$S$ 和 $T$ 均只由小写字母和 `?` 组成。

Output

得分:400分

问题描述

你被给予了由小写英文字母和?组成的字符串$S$和$T$。这里,$|S|>|T|$成立(对于字符串$X$,$|X|$表示$X$的长度)。

长度相等的字符串$X$和$Y$被认为匹配,当且仅当:

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

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

  • 让$S'$是通过不改变顺序地将$S$的前$x$个字符和后$(|T|-x)$个字符连接而得到的长度为$|T|$的字符串。如果$S'$和$T$匹配,则打印Yes,否则打印No

限制条件

  • $S$和$T$是由小写英文字母和?组成的字符串。
  • $1 \leq |T| < |S| \leq 3 \times 10^5$

输入

输入以标准输入的以下格式给出:

$S$
$T$

输出

打印$(|T|+1)$行。
第$i$行应该包含$x=i-1$时的答案。


样例输入1

a?c
b?

样例输出1

Yes
No
No

当$x=0$时,$S'$等于?c。这里,我们可以将$S'$的第1个字符?替换为 b,将$T$的第2个字符?替换为c,使$S'$等于$T$,因此$S'$和$T$匹配。因此,第一行应打印Yes
当$x=1$和2时,$S'$分别是aca?,两者都不匹配$T$。因此,第二行和第三行应打印No


样例输入2

atcoder
?????

样例输出2

Yes
Yes
Yes
Yes
Yes
Yes

样例输入3

beginner
contest

样例输出3

No
No
No
No
No
No
No
No

加入题单

上一题 下一题 算法标签: