[USACO Dec05]可疑的斑点

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file cpattern.in Output file cpattern.out

【题目描述】

约翰的奶牛中有K(1≤K≤25,000)头格外喜欢闹事儿,排队时她们总是站在一起。为了找出她们,约翰让他所有的N(1≤N≤100,000)头奶牛排成一列进入牛棚,并希望你能告诉他队列中的长度为K的可疑群体。

约翰通过斑点数S(1≤S≤25)来辨别奶牛。他已经忘了那些爱闹事的奶牛身上具体有多少个斑点,但仍然记得在这些牛中谁的斑点更多、或者哪些牛的斑点数一样。于是他用一个由斑点数排名构成的序列描述出了这些奶牛排成的队伍。比如说”1,4,4,3,2,1”表示:第一头与最后一头牛斑点数相同,并且比所有其它牛少;第五头牛身上的斑点稍多一些;而第二头和第三头牛拥有最多的斑点。

请你帮助约翰在队伍中找出所有符合描述的子序列。

【输入格式】

第一行输入三个整数N,K,S,接下来N行每行输入一只牛的斑点数。接下来K行每行输入一个排名序列。

【输出格式】

第1行输出一个整数B,即子序列个数。接下来B行每行一个整数,表示一种可能的子序列的起始位置。

【样例输入】

9 6 10

5

6

2

10

10

7

3

2

9

1

4

4

3

2

1

【样例输出】

1

3

【来源】

Brian Dean, 2005

Translate by: 贾由