通配符模式匹配

【题目描述】

给定由小写英文字母和星号（*）构成的字符串 $S$ 和 $T$。

若 $|S'|=|T'|$ 且对每个 $0\leq i<|S'|$ 都满足下列条件之一，则称字符串 $S'$ 与 $T'$ 匹配：

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

对每个 $0\leq i\leq|S|-|T|$，判断 $S[i,i+|T|)$ 与 $T$ 是否匹配。

【输入】

$S,T$

【输出】

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

其中，若 $S[i,i+|T|)$ 与 $T$ 匹配则 $W_i$ 为 $1$，否则为 $0$。

【输入样例】

abc*b*a***a
*b*a

【输出样例】

10111011

【数据范围】

• $1 \leq |T| \leq |S| \leq 524288$
• $S$ 与 $T$ 的每个字符均为小写英文字母或星号。

【来源】

Library Checker（yosupo06） wildcard_pattern_matching