P4696 [CEOI 2011] Matching

For an integer sequence $(a_1,a_2,\cdots,a_n)$ and a permutation $(p_1,p_2,\cdots,p_n)$ of $1 \sim n$, we say that $(a_1,a_2,\cdots,a_n)$ matches $(p_1,p_2,\cdots,p_n)$ if and only if: - Any two numbers in $\{a\}$ are different from each other. - After sorting $(a_1,a_2,\cdots,a_n)$ in increasing order, we obtain $(a_{p_1},a_{p_2},\cdots,a_{p_n})$. Now you are given a permutation $\{p\}$ of $1 \sim n$ and a sequence $h_1,h_2,\cdots,h_m$. Please determine which substrings of $\{h\}$ match the permutation $\{p\}$.

The first line contains two positive integers $n,m$ separated by spaces. The second line contains $n$ positive integers separated by spaces, representing the permutation $p$. The third line contains $m$ positive integers separated by spaces, representing the sequence $h$.

The first line contains an integer $k$, indicating the number of substrings that match $\{p\}$. The second line contains $k$ positive integers separated by spaces, indicating the starting positions of these substrings (indexed from $1$). Output these positions in increasing order. In particular, if $k=0$, you should output an empty line as well.

For $100\%$ of the testdata, $2\le n\le m\le 1\ 000\ 000;1\le h_i\le 10^9;1\le p_i\le n$. It is guaranteed that all elements in $\{h\}$ are pairwise distinct, and $\{p\}$ is a permutation. # Constraints Translated by ChatGPT 5