Usaco problem (contact) in section 2.1

[midra]

Hi! I am stuck with this problem in the usaco training
Maybe someone can help me...

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

if someone can help me I would appreciate very much!
thanks! byee!!

[jakabjr]

hi.

my idea is something like: generate all possible sequences in A-B bit range and convert to a string. use the strstr function to go through the message string and count occurences.
of course, if a=1 and b=12 there are a lot of cases, but there is a catch:
00 will allways have less occurences than 0. the same goes for all duplicates.
so for 1 bit u have 0, 1
for 2 bits u have 01, 10
001 is not eliminated by 01 because there can be as many 001 occurences as 01

otherwise, a solution might be somwhow choosing the sequences to inspect from the message string, though i see no way of doing this... maybe someone else does

[midra]

Thanks for your answer!
I have just one more question:
What is the function strstr????How can I use it??or where can I find information about it??

[neno_uci]

Hi, this is some info gathered from "man strstr", you should understand if you are used to a Linux environment...

STRSTR(3) Linux Programmer's Manual STRSTR(3)



NAME
strstr - locate a substring

SYNOPSIS
#include <string.h>

char *strstr(const char *haystack, const char *needle);

DESCRIPTION
The strstr() function finds the first occurrence of the substring nee-
dle in the string haystack. The terminating `\0' characters are not
compared.

RETURN VALUE
The strstr() function returns a pointer to the beginning of the sub-
string, or NULL if the substring is not found.

BUGS
Early versions of Linux libc (like 4.5.26) would not allow an empty
argument. Later versions (like 4.6.27) work correctly, and return
haystack when needle is empty.

CONFORMING TO
ISO 9899

SEE ALSO
index(3), memchr(3), rindex(3), strchr(3), strpbrk(3), strsep(3), str-
spn(3), strtok(3)



GNU 1993-04-12 STRSTR(3)

hope this helps,

Yandry.

[midra]

thanks a lot!
I am not used to used to a Linux environment
I would try to do the problem now...I hope I can

[nobody10_ca]

The problem is from IOI 98 I think.

If you are program in Windows, MSDN is a great place to look for functions

Have fun solving that problem, if you get to the next section and solve the next couple problems, then you can help me with it

[marcadian]

I have solved this maybe about weeks ago. my idea is to hash the pattern.
but is has problem if the value of bit is same, like 00 and 0, to solve this just simply add '1' in front of the bit so, 00 become 100 and 0 become 10
to sort it I used countingsort, so the bit parttern sorted too from shortest to longest for the same frequency