题目描述

给你两个字符串 $S,T$，其中一些位置为 * 表示可能为任意字符。

求所有 $1 \leq i \leq |T| - |S|+1$，使得 $T[i:i+|S|-1]=S$ 可能成立。

输入格式

输入两行，分别表示字符串 $S,T$.

输出格式

输出一行若干个整数，表示所有匹配的位置，按照从小到大顺序输出。

样例数据

样例 1 输入

a*b
acbc*cb

样例 1 输出

1 5

样例 2 输入

***
*****

样例 2 输出

1 2 3

样例 3 输入

e*e
the*results*of*the*siberian*grand*prix*will*be*added*to*the*rating*after*******gmt*nov****after*the*widesiberian*olympiad*closing*ceremony**where*the*last*hour*for*the*base*contest*teams*will*be*opened*

样例 3 输出

4 44 51 71 73 74 75 76 77 87 88 94 130 132 143 181 192 198 200

子任务

对于所有数据，$1 \leq |S|, |T| \leq 3 \times 10^5$.

• Subtask 1(20 pts): $|S|, |T| \leq 1000$.
• Subtask 2(40 pts): $|S|, |T| \leq 4 \times 10^4$
• Subtask 3(40 pts): No additional constraints.