Want to try solving this problem? You can submit your code online if you log in or register.
Despite your best efforts, your writing is riddled with typos. You are constantly trying to improve, but it is hard work. Luckily, you have just come up with a brilliant solution – you will write a computer program to correct misspelt words!
Your "misspell checker" must be able to take a dictionary of valid words and a message, and correct all the typos. For the purposes of this problem, a typo is a word not in the dictionary which, by replacing a single letter with a different letter, becomes a valid word.
The first line of input will contain a single integer N, indicating the number of words in the dictionary (1 ≤ N ≤ 100,000). Each of the next N lines will contain a single distinct dictionary word. The next line of input will contain a single integer M, indicating the number of words in the message (1 ≤ M ≤ 10,000). Each of the next M lines will contain a single word to be checked. All words will consist of between 1 and 20 lower-case letters, inclusive.
For 30% of the available marks, N,M ≤ 1000. For 60% of the available marks, N ≤ 30,000.
For each of the M message words in the input, your program should output a single line:
9 i apple far mat job for then may apply 6 may i apple fur the jpb
may i apple for ? job
The score for each input scenario will be 100% if a correct answer is written to the output file, and 0% otherwise.
© Australian Mathematics Trust 2001-2023
Page generated: 24 March 2023, 8:28pm AEDT