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:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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