编程题

1698:字符串匹配


时间限制: 1000 ms         内存限制: 262144 KB
提交数:465    通过数: 122

【题目描述】

对于一个字符集大小为$C$的字符串$p$,可以将任意两个字符在$p$中的位置进行互换,例如$p=12321$,交换$1、2$得到$21312$,交换$1、4$得到$42324$,交换可以进行任意次。若交换后$p$变成了字符串$q$,则成$q$与$p$是匹配的。

给定两个字符集大小为$C$的字符串$s、t$,求出$s$中有多少个连续子串与$t$匹配。

【输入】

第一行两个整数$T、C$,分别表示数据组数和字符集大小,字符用$1\\sim C$的整数来表示。

对于每组数据:第一行两个整数$n、m$,分别表示$s、t$的长度。

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

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

【输出】

对于每组数据,输出包括两行:

第一行一个正整数$k$,表示$s$中有$k$个连续子串与$t$匹配。

第二行从小到大输出$k$个数,表示$s$中与$t$匹配的连续子串的首位下标(下标从1开始)。

【输入样例】

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

【提示】

【数据规模及约定】

对于10%的数据,满足$n,m,C≤1000$;

对于另外20%的数据,满足$n,m≤10^5,C≤40$;

对于另外30%的数据,满足$n,m,C≤10^5$;

对于100%的数据,满足$1≤n,m,C≤10^6,T=3$。

查看答案
赣ICP备20007335号-2