#264. 联系

联系

题目背景

奶牛们开始对用射电望远镜扫描牧场外的宇宙感兴趣。最近,他们注意到了一种非常奇怪的脉冲调制微波从星系的中央发射出来。他们希望知道电波是否是被某些地外生命发射出来的,还是仅仅是普通的的星星发出的。

题目描述

帮助奶牛们用一个能够分析他们在文件中记下的记录的工具来找到真相。他们在寻找长度在 AABB 之间(包含 AABB 本身)在每天的数据文件中重复次数前 nn 多的比特序列。

符合的序列可能会重叠,并且至少出现一次的序列会被计数。

输入格式

输入的第一行是三个整数 A,B,nA, B, n,其含义见【题目描述】。

第二行是及以后一个字符串 ss,每行的字符数不超过 8080。所有行的字符串依次连接即为 ss

输出格式

输出 nn 个频率最高的序列(按照频率由高到低的次序)。由短到长排列频率相同的这些序列,如果长短相同,按二进制大小排列。如果出现的序列个数小于 nn,输出存在的序列。

对于每个存在的频率,先输出单独包含该频率的一行,再输出以空格分隔的这些序列。每行六个(除非剩下的少于六个)。

2 4 10
01010010010001000111101100001010011001111000010010011110010000000
23
00
15
01 10
12
100
11
11 000 001
10
010
8
0100
7
0010 1001
6
111 0000
5
011 110 1000
4
0001 0011 1100

提示

在样例里,序列 100100 出现了 1212 次,而序列 10001000 出现了 55 次。次数最多的序列是 0000,出现了 2323 次。

数据范围

对于 100%100\% 的数据,保证 1n501 \leq n \leq 501AB121 \leq A \leq B \leq 12ss 中只含字符 0 和字符 1,且长度不超过 2×1052 \times 10^5