Problem K
Messages from Outer Space
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 words.
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.
Input
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.
Output
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 |
|---|---|
ache ape check peach # checkapeache| animpeachableape| # |
3 2 |
