ZOJ Problem Set - 3056
Aoccdrnig to a rscheearch at Cmabrigde Uinervtisy, it deosn't mttaer in waht oredr the ltteers in a wrod are, the olny iprmoetnt tihng is taht the frist and lsat ltteer be at the rghit pclae. The rset can be a toatl mses and you can sitll raed it wouthit porbelm. Tihs is bcuseae the huamn mnid deos not raed ervey lteter by istlef, but the wrod as a wlohe.
According to a researcher at Cambridge University, it doesn't matter in what order the letters in a word are, the only important thing is that the first and last letter be at the right place. The rest can be a total mess and you can still read it without problem. This is because the human mind does not read every letter by itself but the word as a whole.
The input file first gives the dictionary of the words with length less than 20, ended by a line containing "DICTIONARY_DEFINE_OVER". Then, zero or more lines follow that line, each with a sentence. The sentences contain the messed up words that consist of only lowercase characters. There are punctuations that will only appear at the two ends of some words. NOTE, there will be exactly one original word in the dictionary for each word in the sentences. The size of dictionay is not larger than 10000 and there will be at most 1000 sentences each contains at most 80 characters.
Output the original sentence for each line of sentence in a line.
all luck good fun have
watashi:"really? this fact is amazing~~"
Author: GAO, Yuan
Source: ZOJ Monthly, November 2008