D - Match or Not Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

英小文字と ? からなる文字列 S,T が与えられます。ここで、|S| \gt |T| が成り立ちます(文字列 X に対し、 |X| で X の長さを表します)。

また、|X|=|Y| を満たす文字列 X,Y は、次の条件を満たすとき及びそのときに限りマッチするといいます。

  • X,Y に含まれる ? をそれぞれ独立に好きな英小文字に置き換えることで X と Y を一致させることができる

x=0,1,\ldots,|T| に対して次の問題を解いてください。

  • S の先頭の x 文字と末尾の |T|-x 文字を順番を保ったまま連結することで得られる長さ |T| の文字列を S' とする。S' と T がマッチするならば Yes と、そうでなければ No と出力せよ。

制約

  • S,T は英小文字と ? からなる文字列
  • 1 \leq |T| \lt |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 はマッチします。このため、1 行目の出力は Yes です。
x=1,2 の場合は S' はそれぞれ ac、a? であり、T とマッチしません。このため、2,3 行目の出力は No です。

入力例 2

atcoder
?????

出力例 2

Yes
Yes
Yes
Yes
Yes
Yes

入力例 3

beginner
contest

出力例 3

No
No
No
No
No
No
No
No

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