ZOJ Problem Set - 2828
Have you ever used Microsoft Word (R) to edit English document? Have you noticed the auto-spell-corrector?
Littleboy found that whenever he mistypes the "the" as "teh" or "hte", it will be corrected automatically. Littleboy noticed that people are prone to typing the characters out of order when they type too fast, and he guesses that auto-spell-corrector in Microsoft Word (R) relies on this fact. Being interested in this, he decided to write a simple auto-spell-corrector of his own.
His algorithm works as follow: given a word,
1. If the word can be found from the predefined dictionary, left it as it was.
Input consists of multiple test cases. The first line of the input will be a positive number T(0<T<=10), representing the number of the test cases. Then follow T test cases.
The first line of each test case, there will be an integer D(0<=D<=100), the number of the words in the predefined dictionary. Then D words follow, each word in its own line. After the predefined dictionary, there will be an integer Q(0<=Q<=100), the number of the words that littleboy typed. Again, follow Q words, each in its own line. The length of the word(both in predefined dictionary and littleboy typed) is between 1 and 20, inclusive. All words will only consist of lower case letters ('a'..'z').
For each word littleboy typed, output all the substitution candidates(or the word as it was, depending on which scheme the word matches) in one line, sorted by lexicographically ascending order and separated by a comma(','). So for each testcase, there will be Q lines of output.
Separate two consecutive test cases with a blank line, but Do NOT output an extra blank line after the last one.
2 1 the 3 the teh hte 6 acbed acbde abdce abced badce bcade 3 acbde abcde smith
the the the acbde abced,abdce,acbde smith
Author: SHEN, Guanghao
Source: Zhejiang University Local Contest 2007, Preliminary