HIDDEN CODES
PROBLEM A set of code words and a text are given. The text is supposed to contain a message made up of the code words embedded in the text in a peculiar (and possibly ambiguous) way. The code words and the text are sequences made up of the upper and lower case letters of the English alphabet only. Case-sensitivity is assumed. The length of a code word is defined in the usual way: For example, the code word ALL has length 3. The letters of a code word do not have to occur consecutively in the given text. For example, the code word ALL will always occur in the text within a subsequence in the form of Au LvL where u and v denote arbitrary (possibly empty) sequences of letters. We say that AuLv L is a covering sequence for ALL. In general, a covering sequence for a code word is defined as a subsequence of the text such that the first letter and the last letter of the subsequence are the same as those of the code word and it is possible to obtain the code word by deleting some (possibly none) of the letters of the subsequence. It should be noted that a code word may occur within one or more covering sequences or may not occur in the text at all, and that a covering sequence may be a covering sequence for more than one code word. A covering sequence is identified by its start position (position of its first letter) and its end position (position of its last letter) in the text. (The first letter of the text is at position 1.) We say that two covering sequences, say c 1 and c 2, do not overlap if the start position of c 1 is greater than (>) the end position of c 2 or vice versa. Otherwise we say that the two covering sequences overlap. To extract the message hidden in the text you undertake the task of forming a solution. A solution is a set of items, each consisting of a code word and a covering sequence for this code word, so that the following conditions are all satisfied:
In case there are more than one solution you are required to report only one solution. ASSUMPTIONS
It is guaranteed that in the given text
INPUT There are two input text files: words.inp and text.inp. The words.inp file contains a list of code words and text.inp contains the text.
RECOMMENDATION FOR PASCAL PROGRAMMERS You are advised to declare the input file type as text, as opposed to a typed file for reasons of efficiency. OUTPUT The output must be a text file named codes.out.
EXAMPLE words.inp:
text.inp:
codes.out:
(Remark: The hidden message that could be extracted from the solution is "RuN RaBbit RuN". (An alternative solution would yield "RuN HoBbit RuN"). Be reminded that the message is not to appear on the output. ) EVALUATION Your program will be allowed to run 10 seconds. |