CPATTERN - Cow Patterns

约翰的N(1≤N≤100000)只奶牛中出现了K(1≤K≤25000)只爱惹麻烦的坏蛋。奶牛们按一定的顺序排队的时候，这些坏蛋总会站在一起。为了找出这些坏蛋，约翰让他的奶牛排好队进入牛棚，同时需要你的慧眼来识别坏蛋，为了区分，约翰给所有奶牛都发了号牌，上面写着一个1~S(1≤S≤25)之间的数字。虽然这不是一个完美的方法，但也能起一点作用。现在，约翰已经不记得坏蛋们的具体号码。但是凭他的记忆，他给出一个“模式串”。原坏蛋的号码如果相同，模式串中他们的号码依然相同。模式串中坏蛋们之间号码的大小关系也与原号码相同的。比如，对于这样一个模式串：1，4，4，3，2，1。原来的6只坏蛋，排最前面的与排最后的号码相同（尽管不一定是1），而且他们的号码在团伙中是最小的。第2，3位置的坏蛋，他们的号码也相同（不一定是4），且是坏蛋团伙中最大的。现在所有奶牛排成队列，号码依次是这样：5，6，2，10，10，7，3，2，9存在子串2，10，10，7，3，2，满足模式串的相同关系和大小关系，所以这就是坏蛋团伙，请找出K个坏蛋的困伙的所有可能性。 Input 第1行输入三个整数N，K，S。接下来N行每行输入一只牛的号码。接下来K行每行输入一个模式串的号码。 Output 第1行输出一个整数B。接下来B行，每行一个整数，表示一种可能下的坏蛋团伙的起始位置。 感谢@aoandon 提供的翻译

A particular subgroup of K (1 <= K <= 25,000) of Farmer John's cows likes to make trouble. When placed in a line, these troublemakers stand together in a particular order. In order to locate these troublemakers, FJ has lined up his N (1 <= N <= 100,000) cows. The cows will file past FJ into the barn, staying in order. FJ needs your help to locate suspicious blocks of K cows within this line that might potentially be the troublemaking cows. FJ distinguishes his cows by the number of spots 1..S on each cow's coat (1 <= S <= 25). While not a perfect method, it serves his purposes. FJ does not remember the exact number of spots on each cow in the subgroup of troublemakers. He can, however, remember which cows in the group have the same number of spots, and which of any pair of cows has more spots (if the spot counts differ). He describes such a pattern with a sequence of K ranks in the range 1..S. For example, consider this sequence: ` 1 4 4 3 2 1`In this example, FJ is seeking a consecutive sequence of 6 cows from among his N cows in a line. Cows #1 and #6 in this sequence have the same number of spots (although this number is not necessarily 1) and they have the smallest number of spots of cows #1..#6 (since they are labeled as '1'). Cow #5 has the second-smallest number of spots, different from all the other cows #1..#6. Cows #2 and #3 have the same number of spots, and this number is the largest of all cows #1..#6. If the true count of spots for some sequence of cows is: ` 5 6 2 10 10 7 3 2 9`then only the subsequence 2 10 10 7 3 2 matches FJ's pattern above. Please help FJ locate all the length-K subsequences in his line of cows that match his specified pattern.

Line 1: Three space-separated integers: N, K, and S Lines 2..N+1: Line i+1 describes the number of spots on cow i. Lines N+2..N+K+1: Line i+N+1 describes pattern-rank slot i.

Line 1: The number of indices, B, at which the pattern matches Lines 2..B+1: An index (in the range 1..N) of the starting location where the pattern matches.

9 6 10
5
6
2
10
10
7
3
2
9
1
4
4
3
2
1

1
3