Telephone Numbers

Many New Zealand telephones now have letters printed in association with the digits. This allows firms and organisations to ``customise'' their telephone numbers by incorporating their name or some other word. Thus one might be able to obtain information on training as a nurse by dialling 0-800-NURSING, or find out about courses at local universities by dialling 0-800-4-OTAGOU or 0-800-AUCKUNI.

There are two related problems associated with this approach - one is relatively easy to solve while the other is a little more difficult. If one can elicit the cooperation of one's local telephone company, then one can merely purchase a suitable telephone number that matches your word. However, if you already have a telephone number, then one needs to find the `best' word that matches it.

Write a program that will do this. Input will be a list of words from a dictionary and a list of telephone numbers. Your program must determine suitable candidate words that fit all or part of the given telephone numbers. Since suitability is somewhat subjective the only criterion you should apply is length - only the longest matching words are considered candidates. Note also that matches can only apply at the end, sequences such as 5COSC23 are unacceptable.

For this problem assume the following allocation of letters to digits:

1 Q Z 2 A B C 3 D E F
4 G H I 5 J K L 6 M N O
7 P R S 8 T U V 9 W X Y

Input will consist of two parts. The first part will contain up to 20000 words ranging in length from 4 to 7 upper case letters, one word per line. These words form the dictionary, and will not necessarily be in English. The rest of the file will contain a series of telephone numbers, each containing 7 digits and punctuated conventionally. The file will be terminated by a line consisting of a single #.

Output will consist of a series of lines, one for each number in the input. Each line will consist of the original telephone number, a colon, a space and one or more words or number-word combinations. There must be a hyphen between numbers and letters. If there are several matching words, the words should appear in alphabetic sequence. If there are no matching words, then the message ``No words'' should appear. Follow the spacing and layout shown in the example.

OTAGOU
UBINT
AUCKUNI
MUBGOT
468-2468
123-4567
282-5864
#

468-2468: 4-MUBGOT 4-OTAGOU
123-4567: No words
282-5864: AUCKUNI

ACM暑期集训队练习赛（八）