P10634 BZOJ2372 music

A war has recently broken out between countries A and B. dick, as the commander-in-chief of country A, has been having a headache about intelligence. This is because country B has recently hired a cryptography expert named Easy to encrypt all of their communications. Easy likes singing very much, so he decided to store all signals as melodies. For example, $11556654433221$ could be a sequence of encrypted notes. We represent it with a sequence of the same length, which becomes $1,1,5,5,6,6,\dots$. To increase confidentiality, he further adjusted the encrypted score by changing some pitches, turning the original sequence $A$ into $B$, where $|A|=|B|$, and for $a_i=a_j$ we have $b_i=b_j$, for $a_ib_j$. For example, `11221` and `55775` may represent the same melody. Recently, dick intercepted a signal that may contain important information. Based on past experience, dick already knows what some melodies mean. So dick wants to know: for a known melody, can we determine whether it appears in the intercepted melody? If it does, can we find how many times it appears and at which positions? "Task": Determine the number of occurrences and the positions where the given melody appears in the intercepted melody.

The first line contains three positive integers $n,m,s$. $n$ is the length of the intercepted melody, $m$ is the length of the known melody. All melodies are positive integers in $1\sim s(s\leq 25)$. The next $n$ lines each contain one integer describing the intercepted melody $A$. The next $m$ lines each contain one integer describing the known melody $B$.

The first line contains an integer $t$, the number of occurrences. Then output $t$ lines. In increasing order, give the starting position $p$ of each occurrence, i.e. $A[p\dots p+m-1]$ is equivalent to $B$.

For all testdata, it is guaranteed that $1\leq n \leq 10^5$, $1\leq m \leq 25000$。 Translated by ChatGPT 5