题目描述
给你两个字符串 S,T,其中一些位置为 *
表示可能为任意字符。
求所有 1≤i≤|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≤|S|,|T|≤3×105.
- Subtask 1(20 pts): |S|,|T|≤1000.
- Subtask 2(40 pts): |S|,|T|≤4×104
- Subtask 3(40 pts): No additional constraints.