QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100
[+5]
Statistics

题目描述

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

求所有 1i|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.