A somewhat less glamorous task then that of Agent Fox Mulder
in the X-files is to analyze signals from outer space in search
of messages from possibly subversive extra-terrestrials. Work
of this sort is carried out at FBI’s “Cosmic Ear” division
(Motto: “I want to receive”), and they proceed as follows. A
signal is first translated into a long string of letters. Then
as a first step to finding messages one tries to find as many
substrings as possible that form words. However, these
substrings are not allowed to overlap. For example, “ache” and
“check” are both substrings of “petacheck” but they overlap.
One is not interested in subsequencies only in substrings
(“peach” is a subsequence of “petacheck”, but not a substring).
They have hired you to write the software that finds the
maximum number of non-overlapping substrings that are
Your program will be given a dictionary of words and several
long strings. For each long string, determine the maximum
number of non-overlapping substrings you can find that are
words in the dictionary. If the dictionary consists of the
words “ape” , “peach”, and “check” and the string is
“apeacheckape” then the answer is 3, since you can get the
non-overlapping substrings “ape”, “check”, and “ape” which all
occur in the dictionary.
The input contains a dictionary where each word uses only
lower case characters ‘a’ through ‘z’. Each dictionary word is
on a separate line. All words are at least one and at most ten
characters long. The dictionary is terminated by the character
‘#’ on a separate line. A word is not necessarily a real
English word. The dictionary has no more than $100$ words.
After the dictionary follows a number of “message strings”
(no more than 100). Each message string contains only lower
case characters ‘a’ through ‘z’, but may be broken into several
lines. If so, the line breaks are not part of the string. Each
string is terminated by the character ’|’ which is not itself
part of the string. Finally, the end of the input is marked by
the character ’#’ on a separate line. Most message strings are
fairly short, but some can have as many as $50\, 000$ characters.
For each message string, output on a separate line the
maximum number of non-overlapping substrings that can be found
in the dictionary.
|Sample Input 1
||Sample Output 1