와일드카드 패턴 매칭

영문 소문자와 별표(*)로 구성된 문자열 $S$와 $T$이 주어진다.

문자열 $S'$와 $T'$가 $|S'|=|T'|$이고 다음 중 하나를 만족하면 두 문자열이 매칭된다고 한다.

• $S'_i$ = $T'_i$
• $S'_i$ = *
• $T'_i$ = *

이는 각 $0\leq i<|S'|$에 대해 성립한다.

각 $0\leq i\leq|S|-|T|$에 대해, $S[i,i+|T|)$와 $T$가 매칭되는지 구한다.

제약 조건

• $1 \leq |T| \leq |S| \leq 524288$
• $S$와 $T$의 각 문자는 영문 소문자 또는 별표이다.

$S,T$

$W_0, W_1, \dots, W_{|S|-|T|}$

여기서 $S[i,i+|T|)$와 $T$가 매칭되면 $W_i$은 $1$이고, 그렇지 않으면 $0$이다.