P4173 Incomplete Strings

Long ago, when you had just learned string matching, there were two strings $A$ and $B$ containing only lowercase letters, with lengths $m$ and $n$ respectively. Now, when you encounter these two strings again, they have aged; each string has become partially damaged. You want to match the two strings again, taking $A$ as the pattern. For every position $i$ in $B$, determine whether the length-$m$ substring starting at this position could exactly match string $A$.

The first line contains two positive integers $m, n$, representing the lengths of strings $A$ and $B$ respectively. The second line contains a string $A$ of length $m$. The third line contains a string $B$ of length $n$. Both strings consist only of lowercase letters and $\texttt *$, where $\texttt *$ indicates that the corresponding position is damaged and each $\texttt *$ can match any single lowercase letter.

The first line contains an integer $k$, the number of starting positions in $B$ where $A$ can exactly match. If $k > 0$, then on the second line output $k$ positive integers in increasing order, each being a valid starting position (indices start from $1$).

For $100\%$ of the testdata, $1 \le m \le n \le 3 \times 10^5$. Translated by ChatGPT 5