2007/2008 SOUTHERN CALIFORNIA REGIONAL
ACM INTERNATIONAL COLLEGIATE PROGRAMMING CONTEST

Problem 4
Domain Name Follies

With the explosion of Internet access and commerce over the past decade, there has been a huge demand for organization domain names. Several words are often strung together to form a second-level domain name (the name to the left of the top-level .edu, .com, .org, ¼ domain). Names are limited to 63 characters, and although hyphens are allowed, most domain name owners avoid them so the names are shorter and easier to type. However, since domain names are case-insensitive, alternate readings of such names are sometimes possible, and there have been occasional cases where an alternate reading was embarassing for the domain owner. This has happened even when the name was not initially seen as a word sequence strung together.
Your team has been commissioned to develop a program that will take suggested domain names and compare them against the words in a dictionary. The program is to determine if a domain name can be split entirely into words that exist in the dictionary, and make particular note if such a split includes "questionable" words. The potential domain owner can then decide if (s)he wants to change the name, perhaps by inserting hyphens at desired points or even rewording the name entirely. Note that a domain owner is interested in every possible word split, regardless of whether or not the result makes sense as a phrase.
Input to your program will be in two sections. The first section contains the word dictionary, one word per line. Any word that is considered "questionable" will be listed with a question mark in the first column. Words that are not questionable will have a space in the first column. Each word in the dictionary will appear in lower case (letters a-z) starting in the second column. Variations of a word (such as "run," "runs," and "runner") will be listed separately. Words will each be unique and will appear in no particular order. No word is longer than 32 characters. The word list could contain up to 20,000 words. The dictionary will end with an empty line.
The remaining input will be a list of proposed second-level domain names in all lower case, one per line, each starting in the first column. This list will end with the end-of-file.
For each proposed second-level domain name, your program is to print a list of all the possible word sequences that make up the domain name. The proposed name should appear on a line by itself, starting in the first column, immediately followed by a colon. The word sequences should appear in alphabetical (ASCII) order, one per line. If a given word sequence contains a questionable word, the first column is to contain a question mark; if no word in the sequence is questionable, the first column is to contain a space. The word sequence is to be printed starting in the second column, with hyphens separating the words from each other.
If a given domain name cannot be split into a sequence of dictionary words, print an exclamation mark in the first column, followed by the message "No word sequence found." starting in the second column.
No output line is to include trailing whitespace.
Print an empty line after the results for each domain name (including the last).

Sample Input

 word
 words
 together
 and
 a
 ?darn
 ?swear
 strung
 the
 an
 wear
 boys
 boy
 
 wordsstrungtogether
 boyswear
 notindictionary


Output for the Sample Input

 wordsstrungtogether:
 words-strung-together
 
 boyswear:
 ?boy-swear
 boys-wear
 
 notindictionary:
 !No word sequence found.



File translated from TEX by TTH, version 3.77.
On 17 Nov 2007, 22:23.