#P1461. 字符串的匹配

字符串的匹配

题目描述

给出长度为 nn 的整数串 AA 和长度为 mm(m≤nm\le n)的整数串 BB,元素均为不大于 ss 的正整数。两个等长串被认为匹配,当且仅当它们在每个位置的元素具有相同的相对大小关系;即任意两位置 i,ji,j 的小于、等于、大于关系都相同。

例如 (1,2,3,5,4)(1,2,3,5,4) 与 (8,10,23,25,24)(8,10,23,25,24) 匹配。求 AA 中所有长度为 mm 且与 BB 匹配的子串。

输入格式

第一行三个整数 n,m,sn,m,s。接下来 nn 行,每行一个整数,依次表示 AA;再接下来 mm 行,每行一个整数,依次表示 BB。

输出格式

第一行输出匹配子串数量 pp。接下来 pp 行按从小到大输出每个匹配子串首元素在 AA 中的位置,位置从 11 开始编号。

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

提示

对于 20%20\% 的数据,n≤10000n\le10000;对于全部数据,n≤500000n\le500000,m≤25000m\le25000,s≤10000s\le10000。