ACM Regional Programming Contest 1998
Problem No.  6  -Spell Checker
Executable Program: PROG6.EXE, PROG6.CLASS
Source Program: PROG6.CPP, PROG6.C, PROG6.PAS, PROG6.JAVA
Input file: IN.TXT   Output file: OUT.TXT

    Problem Description: Your program will receive as input  two different word lists: the first one should be taken as the dictionary, (it doesn’t  matter if the words in this first list are correctly spelled or not) and the second list are possibly misspelled words, to be checked against the dictionary.

    Your program should decide for each word of the list to be checked, the “best fit” from the words in the dictionary in terms of these criteria:

    1. The checking word and the dictionary word should have the closest set of characters in common.

    2. A minimum of displacements should be done to move each character in the checking word to the position it has in the selected dictionary word. Displacements could be to the left or to de right.

    3. If a character in the checking word is not in the dictionary word, consider it should be moved a number of positions equal to the length of the word.

    For example, if the dictionary includes the words call, close, closed and the word to check is dclso, the evaluation is as follows:
 
 

Dictionary word 
Diff.
#Diff.
d
l
Total 
Call
d,l,s,o
5r 
1l
5r
5r
20 
Close
d,e
2
5r 
1l 
1l
 0 
2l 
11 
Closed
e
1
5r 
1l 
1l
0
2l 
9 
  
    In this table, 1r means that a character should be moved one position to the right to reach its correct position in the dictionary word, 2l means that the character should be moved two positions to the left, and so on. Note that when a character in the word to check doesn’t match a character in the dictionary word, its considered to be moved 5 positions to the right (the length of the checking word). The total cost is calculated only in terms of the magnitude of the displacements and the number of different characters, it doesn’t matter if they are missing or extra characters. In this example, the dictionary word with the minimum cost is closed, so this is the word to be suggested as the correction for dclso.
Input file description

    There is a word per line, and no more than a thousand words in each list. The dictionary list and the checking list are separated just with one empty line. The input file ends with the last word to be checked.  There should not be any assumptions about the sorting order of the words in both lists. On the other hand, you can assume that words in both lists are always in lower case, that length is at least one and no more than one hundred characters, and that characters are just from ‘a’ to ‘z’ (no special characters, nor blanks or numbers). In the example shown, the words from “silly” to “wheel” are the dictionary and those from “prctnrcio” to “heewl”, are the words to checked.
 
Input file example:
silly
easily
good
practice
practicioner
goal
spelling
well
wheel

prctnrcio
rpacteci
lingspel
doog
gaool
sill
easill
wll
heewl
 

Output file description
You should print a line for each word to be checked, followed by a colon and the word from the dictionary selected by your program with no leading, intermediate or following blanks. The output file shown is the expected output for the input file.

Output file example:

**********************
* Team ##, Problem 6 *
**********************

prctnrcio:practicioner
rpacteci:practice
lingspel:spelling
doog:good
gaool:goal
sill:silly
easill:easily
wll:well
heewl:wheel