Contact
IOI'98
The cows have developed a new interest in scanning the universe
outside their farm with radiotelescopes. Recently, they noticed a very
curious microwave pulsing emission sent right from the centre of the
galaxy. They wish to know if the emission is transmitted by some
extraterrestrial form of intelligent life or if it is nothing but the
usual heartbeat of the stars.
Help the cows to find the Truth by providing a tool to analyze bit
patterns in the files they record. They are seeking bit patterns of
length A through B inclusive (1 <= A <= B <= 12)
that repeat themselves most often in each day's data file. They are
looking for the patterns that repeat themselves most often. An input
limit tells how many of the most frequent patterns to output.
Pattern occurrences may overlap, and only patterns that occur at
least once are taken into account.
PROGRAM NAME: contact
INPUT FORMAT
| Line 1: |
Three space-separated integers: A, B, N; (1
<= N < 50) |
| Lines 2 and beyond: |
A sequence of as many as 200,000
characters, all 0 or 1; the characters are presented 80 per line, except
potentially the last line. |
SAMPLE INPUT (file contact.in)
2 4 10
01010010010001000111101100001010011001111000010010011110010000000
In this example, pattern 100 occurs 12 times, and pattern 1000 occurs
5 times. The most frequent pattern is 00, with 23 occurrences.
OUTPUT FORMAT
Lines that list the N highest frequencies (in descending order of
frequency) along with the patterns that occur in those frequencies.
Order those patterns by shortest-to-longest and increasing binary number
for those of the same frequency. If fewer than N highest frequencies
are available, print only those that are.
Print the frequency alone by itself on a line. Then print the actual
patterns space separated, six to a line (unless fewer than six remain).
SAMPLE OUTPUT (file contact.out)
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
题意：
给出一个只含'0'或'1'的字符串。
求出字符串中长度在A到B之间的各个子串出现个数；
/*
LANG: C
TASK: contact
*/
#include<stdio.h>
#define maxn 200001
char str[maxn], p[maxn], q[13];
int T[maxn], h = 0;
typedef struct N
{
int cnt, len;
char q[13];
}M;
M N[10000];
int cmp(const void * a, const void * b)
{
if ( ((M*)a)->cnt == ((M*)b)->cnt )//比较出现次数
{
if (((M*)a)->len == ((M*)b)->len)//比较长度
{
return strcmp(((M*)a)->q, ((M*)b)->q);//比较字典序
}
return ((M*)a)->len - ((M*)b)->len;
}
return ((M*)b)->cnt - ((M*)a)->cnt;
}
void insert(int k, int num)//插入字符
{
if (p[k])
{
if (p[k] - '0')//如果p[k]是'1'，则往右走
{
insert(k + 1, (num << 1) + 1);
}
else//否则，往左走
{
insert(k + 1, num << 1);
}
}
}
void in()
{
if (p[0] - '0')
{
insert(1, 3);
}
else
{
insert(1, 2);
}
}
void pre(int k, int num, int L)
{
if (T[num])//
{
if (num % 2)
{
q[k++] = '1';
}
else
{
q[k++] = '0';
}
q[k] = 0;
if (k >= L)//对长度允许的字串保存
{
strcpy(N[h].q, q);
N[h].len = k;
N[h++].cnt = T[num];
}
pre(k, num << 1, L), pre(k, (num << 1) + 1, L);//遍历左子树和右子树
}
}
int main()
{
freopen("contact.in", "r", stdin);
freopen("contact.out", "w", stdout);
char s[81];
int L, R, n, t, len, i, j, k, l;
scanf("%d%d%d", &L, &R, &n);
getchar();
while (gets(s))
{
if (strcmp(s, "") == 0)
{
break;
}
strcat(str, s);
}
len = strlen(str);
for (i = 0; i < len - L + 1; i++)
{
for (j = 0, k = i; j < R && str[k] != 0; j++, k++)
{
p[j] = str[k];
if (j >= L - 1)
{
p[j+1] = 0;
}
}
in();//插入p
}
pre(0, 2, L), pre(0, 3, L);//因为开始'0'是从数组T[2]进入,'1'是从T[3]进入，所以分成两颗树了
qsort(N, h, sizeof(M), cmp);
for (i = 0, k = 0; i < h && k < n; i = j, k++)
{
printf("%d\n", N[i].cnt);
printf("%s", N[i].q);
for (j = i + 1, l = 1; j < h && N[j].cnt == N[i].cnt; j++, l++)//找出现次数相同的输出
{
if (l == 6)//每六个一行
{
l = 0;
printf("\n%s", N[j].q);
}
else
{
printf(" %s", N[j].q);
}
}
printf("\n");
}
fclose(stdin), fclose(stdout);
//system("pause");
return 0;
}