50011. Spell Checker

I'm a slow walker, but I never walk backwards.

Problem description

Write a simple spell checker. First you will read a set of words as a dictionary. Next you will read a set of word as text. For example our dictionary has apple, apples, orange, banana. All words are in lower case from 'a' to 'z' only.

For every word in text you must look up the dictionary and determine if the spelling is correct. If the word from text is in the dictionary, like apple, then you output a line >apple.

If the word from text is not in the dictionary, you must list all possible candidates as ?apple apples, in the order they appear in the dictionary. A word in the dictionary is a candidate if one of the following is true.

  1. If we replace a character in the candidate, it becomes the word in text. Note that we can only change one character, so apple is not a candidate of aqqle.
  2. If we add a character into the candidate, it becomes the the word in text. Note that a character could be removed from every possible position, so apple is a candidate of appple.
  3. If we remove a character from the candidate, it becomes the word in text. Note that a character could be added into every possible position, so apple is a candidate of aple.

If you cannot find any candidate, simply output !aple.

Subtasks

  • 25pt. The word is either in the dictionary, or is not in the dictionary and no candidates can be found.
  • 25pt. You only need to consider candidates with the first condition if the word is not in the dictionary.
  • 25pt. You only need to consider candidates with the first and the second conditions if the word is not in the dictionary.
  • 25pt. You need to consider candidates of all three conditions if the word is not in the dictionary.

Input Format

The first line contains an integer $N$ denoting the number of words in the dictionary. Followed by $N$ lines, each line contains a word $w_i$ denoting the $i$-th word in the dictionary. After $N+1$ lines, the next line contains an integer $Q$ denoting the number of words in text. Followed by $Q$ lines, each line contains a word $q_i$ denoting the $i$-th word in text.

  • $N \le 200, \; \sum \vert w_i\vert \le 10000, \; \vert w_i\vert \le 100, \; Q \le 20, \; \vert q_i\vert \le 20 $ for 95% testdata.
  • $N \le 100000, \; \sum \vert w_i\vert \le 1000000, \; \vert w_i\vert \le 100, \; Q \le 1000, \; \vert q_i\vert \le 100 $ for 100% testdata.

Sample Input 1

1
apple
1
applz

Sample Output 1

?apple

Sample Input 2

2
apple
apples
1
applez

Sample Output 2

?apple apples

Sample Input 3

5
case
content
contest
common
onganize
4
cases
common
context
come

Sample Output 3

?case
>common
?content contest
!come

Recommended

// (O)
int n = strlen(s);
for (int i = 0; i < n; i++) {
}
 
// (X) will let you TLE!
for (int i = 0; i < strlen(s); i++) {
}

Discussion