Spelling Suggestion

A spelling suggestion is the part of a spelling-correction program that proposes plausible replacements for a word that is likely misspelled. One way to rank these replacements is by their edit distance to the misspelled word: the total cost of the edit operations needed to turn one word into the other.

The allowed edit operations and their costs are:

• Insertion of a single character: cost 2.
• Deletion of a single character: cost 2.
• Transposition of two adjacent characters: cost 2.
• Substitution of one character with another: cost 1 if the two characters are near on the keyboard (near-substitution), otherwise cost 2 (far-substitution). Leaving a matching character unchanged costs 0.

For example, starting from wonder: deleting the o gives wnder; substituting the o with a gives wander; transposing er gives wondre.

The minimum edit distance between two words is the smallest total cost over all sequences of operations. A dictionary word with a smaller minimum edit distance to the input word is a better spelling suggestion.

Which pairs of characters count as near is given by a set of near-substitution rules (based on an English QWERTY keyboard layout). Near-substitution is symmetric: if character y is listed as near-substitutable for character x, then substituting x with y and substituting y with x both cost 1.

For every input word, report the dictionary word(s) with the least minimum edit distance from it.

The input is read from standard input and has three parts. Each part ends with a blank line, so the blank line after the third part terminates the input.

Part 1 — near-substitution rules (at most 150 lines). Each line holds two fields separated by a single space:

• The first field is a single character.
• The second field is a sequence of characters (no spaces) that are near-substitutable with the first character.

Near-substitution is symmetric. The characters that may appear in this part are the alphanumeric characters and punctuation that can be typed on a generic English keyboard (no space or tab):

abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789`~!@#$%^&*()-_=+\|[{]};:',<.>/?

Part 2 — dictionary (at most 150,000 words), one word per line. Dictionary words use the letters below plus the apostrophe ('):

abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

Part 3 — words to check (at most 5,000 words), one word per line. These words use the same character set as Part 1.

For each word in Part 3, print one line with three fields separated by colons (:):

• The input word.
• The minimum edit distance between the input word and its nearest dictionary word(s).
• The suggestion word(s): every dictionary word that achieves that minimum edit distance, listed in ascending order and separated by single spaces, with no trailing space.

Ordering is by character code (byte/ASCII order), so digits come before uppercase letters, which come before lowercase letters.