training_2003_11_17 - Fancy substring

Problem F. Fancy substring ≡

problems
visible spaces
basic formulae
wide text
editor

Author:	M. Sporyshev, A. Klenin, A. Baranov	Time limit:	1 sec
Input file:	input.txt	Memory limit:	256 Mb
Output file:	output.txt

Statement

String T consists of small Latin letters. String P consists of small Latin letters and star symbols '*'.

Your program must find all positions in T where some cyclic shift of P occurs (that is, indexes s, for which there exists d such that P_{(i + d) mod |P|} = T_s + i, i = 0, |P| − 1).

Additionally, star in P may correspond to an arbitrary single character in T.

Input file format

First line of input file contains string T. Second line of input file contains string P.

Output file format

Output file must contain an integer K — number of positions, followed by K integers a_i — position indexes in ascending order. Positions are indexed from zero.

Constraints

1 ≤ |T| ≤ 10⁵

1 ≤ |P| ≤ 400

|P| ≤ |T|

Number of star symbols in P doesn't exceed 3.

Sample tests

No.	Input file (`input.txt`)	Output file (`output.txt`)
1	`abacaba bca`	`1 3`
2	`abacaba a*a`	`3 0 2 4`