Processing math: 30%

Problem F. Fancy substring

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 = \overline{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 \le |T| \le 10^5

1 \le |P| \le 400

|P| \le |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

0.057s 0.009s 13