P6080 [USACO05DEC] Cow Patterns G

Among Farmer John’s $N$ cows ($1 \leq N \leq 10^5$), there are $K$ troublemakers ($1 \leq K \leq 25000$)! These troublemakers always stand together when the cows line up. Now you need to help FJ find them. To tell cows apart, FJ gave each cow a tag with a number between $1 \ldots S$ ($1 \leq S \leq 25$). Although this is not a perfect method, it still helps. Now FJ cannot remember the exact numbers of the troublemakers, but he provides a pattern sequence. If some troublemakers had the same number in the original group, then the corresponding numbers in the pattern sequence are still the same. Also, the relative ordering of the numbers in the pattern sequence is the same as in the original group. For example, for the pattern sequence: $1,4,4,3,2,1$, in the original group of $6$ troublemakers, the first and last numbers are equal and are the smallest (not necessarily $1$), and the troublemakers at positions $2,3$ have the same number and are the largest (not necessarily $4$). Now consider this lineup: $5, 6, 2, 10, 10, 7, 3, 2, 9$. Its substring $2, 10, 10, 7, 3, 2$ matches the equality relationships and size relationships of the pattern sequence, so it could be a troublemaker group. Find all possible locations of such groups.

The first line contains three integers $N, K, S$. The next $N$ lines each contain one integer, representing the tag number of the $i$-th cow. The next $K$ lines each contain one integer, representing the number at position $i$ in the pattern sequence.

The first line outputs an integer $B$. The next $B$ lines each contain one integer, the starting position of one possible troublemaker group. Output all positions in increasing order.

Translated by ChatGPT 5