| Author: | M. Sporyshev, A. Klenin, A. Baranov | Time limit: | 1 sec | |
| Input file: | input.txt | Memory limit: | 256 Mb | |
| Output file: | output.txt |
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| = Ts + i, i = 0, |P| − 1).
Additionally, star in P may correspond to an arbitrary single character in T.
First line of input file contains string T. Second line of input file contains string P.
Output file must contain an integer K — number of positions, followed by K integers ai — position indexes in ascending order. Positions are indexed from zero.
1 ≤ |T| ≤ 105
1 ≤ |P| ≤ 400
|P| ≤ |T|
Number of star symbols in P doesn't exceed 3.
| No. | Input file (input.txt) |
Output file (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|