UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#1892. Match

统计 下载数据

Description

PP发明了一种新的串匹配! 给出一个长度为N的整数串A,和一个长度为K(K<=N)的整数串B,A和B中的元素均是不大于S的正整数,我们认为两个串是相等的,当两个串的长度相当,并且两个串中,对于任意的i,第i个元素在两个串中的排名是一样的。 例如: 1 2 3 5 4 8 10 23 25 24 这两个串是相等的。 现在要求在A的所有长度=B的长度的子串中,有多少子串与B串相等。

Input

第一行三个整数N,K,S。 第二行N个整数表示A串。 第三行K个整数表示B串。

Output

第一行一个P表示A串中一共有多少个子串和B串相等, 接下来P行从小到大每行一个整数,表示和B串相等的A串的子串的第一个元素的位置。

Sample Input

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

Sample Output

1
3

数据规模:
对于20%的数据N<=10000
对于100%的数据N<=500000,S<=10000

Hint

 题解http://pan.baidu.com/s/1mgW2sFA

Source

By Mt