b773: 50011. Spell Checker
Tags : 字串處理
Accepted rate : 4人/5人 ( 80% ) [非即時]
評分方式:
Tolerant

最近更新 : 2016-01-13 14:32

Content

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.

Input

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 |w_i| \le 10000, ; |w_i| \le 100, ; Q \le 20, ; |q_i| \le 20 $ for 95% testdata.
  • $N \le 100000, ; \sum |w_i| \le 1000000, ; |w_i| \le 100, ; Q \le 1000, ; |q_i| \le 100 $ for 100% testdata.
Output
Sample Input
5
case
content
contest
common
onganize
4
cases
common
context
come
Sample Output
?case
>common
?content contest
!come
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (4%): 1.0s , <1K
公開 測資點#1 (4%): 1.0s , <1K
公開 測資點#2 (4%): 1.0s , <1K
公開 測資點#3 (4%): 1.0s , <1K
公開 測資點#4 (4%): 1.0s , <1K
公開 測資點#5 (4%): 1.0s , <1K
公開 測資點#6 (4%): 1.0s , <1K
公開 測資點#7 (4%): 1.0s , <1K
公開 測資點#8 (4%): 1.0s , <1K
公開 測資點#9 (4%): 1.0s , <1K
公開 測資點#10 (5%): 1.0s , <1K
公開 測資點#11 (5%): 1.0s , <1K
公開 測資點#12 (5%): 1.0s , <1K
公開 測資點#13 (5%): 1.0s , <1K
公開 測資點#14 (5%): 1.0s , <1K
公開 測資點#15 (5%): 1.0s , <1K
公開 測資點#16 (5%): 1.0s , <1K
公開 測資點#17 (5%): 1.0s , <1K
公開 測資點#18 (5%): 1.0s , <1K
公開 測資點#19 (5%): 1.0s , <1K
公開 測資點#20 (5%): 1.0s , <1M
公開 測資點#21 (5%): 1.0s , <1M
Hint :
Tags:
字串處理
出處:
NTU批改娘計算機程式設計課程 [管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」