Spelling Suggestion#3100
A spelling suggestion is a part of a spelling correction program that generates a set of plausible replacements for words that are likely to be misspelled. One way to measure the plausibility of these replacements is to compute their edit distance against a given misspelled word. The edit distance between two words is the total number of edit operations that must be performed to transform one word into the other. Normally, these edit operations are insertion, deletion, and substitution of a single character, including the transposition of consecutive characters.
For example, for the word "wonder", if the deletion is applied at the character 'o', this word will transform into "wnder". If substitution with 'a' is applied at 'o', it will become "wander". If transposition is applied at "er", it will become "wondre".
In this edit distance strategy, the degree of similarity between two words is determined by their minimum edit distance. If the minimum edit distance between word_1 and word_2 is less than that between word_1 and word_3, then word_1 is more similar to word_2 than to word_3. So, word_2 is a better spelling suggestion for word_1 compared to word_3.
Suppose you work for a software company that needs to develop a prototype spelling suggestion program. This prototype will be a part of a word processing application. The requirement is that it must use the edit distance strategy for spelling suggestions. However, the substitution operation should be adapted to more closely reflect typing errors. The cost of substituting one character for another depends on their position on the keyboard. If the characters are close together on the keyboard layout, the cost is only half of the standard substitution cost. For this purpose, substitution is categorized into near-substitution and far-substitution. Their costs are defined as and , respectively. The costs for insertion, deletion, and transposition are . In addition, this program must be fast enough to meet the time limit set by your manager. For this prototype, the English QWERTY keyboard layout is selected.
Goal
Generate the optimal spelling suggestions for each input word, where each optimal spelling suggestion is a word in the dictionary that has the smallest edit distance from the given input word. The time limit for misspelled words is less than or equal to minutes.
The input is standard input and consists of parts. Each of these three parts ends with a blank line.
The first part contains the set of near-substitution rules, with each rule on a separate line. Each line has two fields separated by a space. The total number of rules is at most .
The first field is a character that can be near-substituted with other characters.
The second field is a sequence of characters that can be near-substituted for the character in the previous field. There are no spaces in this field.
The symbols that can appear in this part are those that can be typed on a generic English keyboard layout: alphanumeric characters and some punctuation marks, without spaces or tabs. They are listed as follows.
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789' !@#$%^*()-_=+|[{}];:'",<.>/?
The second part is a list of dictionary words, one per line. The total number of words does not exceed .
Allowed characters for dictionary words are alphabetic characters and the apostrophe (').
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
The third part is a list of words that need spelling suggestions, with one word per line. The total number of words does not exceed .
The characters that may appear in this part are the same as those in the first part: alphanumeric characters and some punctuation. (See the first part.)
Since each of these three parts ends with a blank line, the third blank line signals the end of the input.
For each word in the third part, output a line containing pieces of information separated by a colon:
The first is the original input word.
The second is the minimum edit distance between the input word and the suggested word(s).
The third is a space-separated list of suggested word(s), sorted in ascending order, with no extra space after the last word.
Further Explanation
In the sample input, there are near-substitution rules (lines 1-5), words in the dictionary (lines 7-16), and words seeking spelling suggestions (lines 18-29).
In the sample output, there are lines for the corresponding input words.
For the 1st word, the minimum edit distance between x and its suggestions (A B Z a b) is . All these are far-substitution costs.
For the 2nd word, the minimum edit distance between s and its suggestion (a) is —a near-substitution cost guided by the first substitution rule.
For the 3rd word, the minimum edit distance between z and its suggestions (A Z a) is , by either the first or the fifth substitution rule.
For the 4th word, the minimum edit distance is , comprising one far-substitution and one deletion cost.
For the 5th word, the minimum edit distance is : costs between xxx and (A B Z a b) come from two deletions and one far-substitution; costs between xxx and ABC are from three far-substitutions.
For the 6th word, the cost between angre and anger is from one transposition; the cost between angre and (angle angry) is from one far-substitution.
For the 7th and 8th words, the cases look similar. For the 7th word, the cost is one far-substitution. For angrt and anger, the cost is two near-substitution costs (r substituted with e and t with r), according to the fourth near-substitution rule.
For the 9th word, the word matches the dictionary exactly; so the cost is .
For the 10th and 11th words, their costs are each one transposition.
For the 12th word, the cost between CAB and (A B) involves two deletions; between CAB and (ABC) it is one deletion plus one insertion. Note this does not come from two transpositions from CAB to ACB, then ACB to ABC.
Example 1