当前没有测试数据。

4.字符串匹配

题目描述

对于一个字符集大小为$C$的字符串$P$，我们可以将任意两种字符在$P$中的位置进行互换，例如$P=abcba$，我们交换$a$，$b$就变为$bacab$，交换$a$，$d$就变为$dbcbd$，交换可以进行任意次。若交换后$P$变为了字符串$Q$，则我们称$Q$与$P$是匹配的。

现在给定两个字符集大小为$C$的字符串$S$，$T$，请你求出$S$中有多少个连续子串与$T$是匹配的。

输入格式

第一行两个整数$Case$,$C$表示数据组数与字符集大小。字符用$1$~$C$的整数来表示。

每组数据第一行两个整数$n$，$m$表示$S$的长度与$T$的长度。

第二行$n$个正整数表示$S$。

第三行$m$个正整数表示$T$。

输出格式

对于每组数据输出两行。

第一行一个正整数$ans$，表示$S$中有多少个连续子串与$T$匹配。

接下来一行从小到大输出$ans$个整数，表示$S$中与$T$匹配的连续子串的首位置。

数据范围

• 对于$10\%$的数据：$n,m,C \leq 1000$
• 另有$20\%$的数据：$n,m \leq 10^5$，$C \leq 40$
• 另有$30\%$的数据：$n,m,C \leq 10^5$
• 对于$100\%$的数据：$1 \leq n,m,C \leq 10^6$，$Case = 3$

样例

3 3
6 3
1 2 1 2 3 2
3 1 3
6 3
1 2 1 2 1 2
3 1 3
6 3
1 1 2 1 2 1
3 1 3

3
1 2 4
4
1 2 3 4
3
2 3 4