1997 Canadian Computing Competition, Stage 1

Problem D: Dynamic Dictionary Coding

A common method of data compression, "dictionary coding", is to replace words in a text by numbers indicating their positions in a dictionary. Static dictionary coding, in which the dictionary is known in advance, can be problematic, as it is necessary to have the dictionary available to understand the coded text. Dynamic dictionary coding avoids this problem by deriving the dictionary from the text to be compressed. The text is processed from beginning to end, starting with an empty dictionary. Whenever a word is encountered that is in the dictionary, it is replaced by a number indicating its position in the dictionary. Whenever a word is encountered that is not in the dictionary, it appears as-is in the compressed text and is added to the end of the dictionary.

You are to implement dynamic dictionary coding. See the input and output specifications below.

Input

The first line of the input file contains a positive integer which is the number of sets of text which are to be compressed. Each set of text will consist of several lines containing text made of lower case letters and spaces only. You may assume that no word is longer than 20 letters, that no input line is longer than 80 characters, and that there are no more than 100 input lines. The sets of text are separated by a single blank line, and are to be compressed individually.

Output

The output file should contain the sets of text input compressed using dynamic dictionary coding as described above. Lineation and spacing should be preserved exactly as in the input file with the different sets of compressed text separated by a single blank line.

Sample Input

1
the cat chased the rat while
the dog chased the cat into the rat house

Sample Output

the cat chased 1 rat while
1 dog 3 1 2 into 1 4 house

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 28, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Does the judge give the blank lines through raw_input? And does it give a blank line at the very end?

yeesss

Does anyone know how to detect a blank line in java because .equals("") doesn't seem to work? 

Thanks

This comment falls under the section in the commenting rules:
[quote]if there's something you don't understand about your programming language, ask it on IRC[/quote]

That said: both
[code]str.equals("")[/code] and the preferred way
[code]str.isEmpty()[/code] work.

The issue with your code lies somewhere else; try making more test data.

str.equals("")

str.isEmpty()

How do we handle just one case?

Is there a blank line at the end? Or...

The judge doesn't care about blank lines.
See the Help page for more info.

First input [b]T[/b], the number of test cases to follow.
Then, input a few lines. Each test case is separated by a blank line.
e.g. if T were 2, it wouldn't be
[color=blue]the dog chased the cat
the cat chased the rat
the rat chased the cheese
the mouse was in the house
that was a house for a mouse[/color]
; it would be
[color=blue]the dog chased the cat
the cat chased the rat
the rat chased the cheese

the mouse was in the house
that was a house for a mouse[/color]

Hope it helps.