Задачі
Spelling Suggestion
Spelling Suggestion
A spelling suggestion is a part of spelling correction program that generates a set of plausible replacements for words that are likely to be misspelled. One way to measure the plausibility of these replacements is to compute their edit distance against a given misspelled word. The edit distance between two words is the total number of edit operations that have to be done in order to transform one word into the other. Normally these edit operations are insertion, deletion and substitution of a single character including transposition of \textbf{2} consecutive characters.
For example, for a word "\textbf{wonder}", if the deletion is applied at the character '\textbf{o}', this word will transform into "\textbf{wnder}". And if the substitution with '\textbf{a}' is applied at '\textbf{o}', it will become "\textbf{wander}". And if the transposition is applied at "\textbf{er}", it will become "\textbf{wondre}".
In this edit distance strategy, the degree of similarity between two words is up to their minimum edit distance. If the minimum edit distance between \textbf{word_1} and \textbf{word_2} is lower than the distance between \textbf{word_1} and \textbf{word_3}, then \textbf{word_1} is more similar to \textbf{word_2} than to \textbf{word}
Вхідні дані #1
a AqQzZsS b BgGvVnN p P0);:oO[{ r R4$fFeEtT z ZaAxX a A b B Z angel angle anger angry ABC x s z xx xxx angre angri angrt angel ACB BAC CAB
Вихідні дані #1
x:2:A B Z a s:1:a z:1:A Z a xx:4: A B Z a b xxx:6:A ABC B Z a b angre:2:anger angle angry angri:2:angry angrt:2:anger angry angel:0:angel ABC:2:ABC BAC:2:ABC CAB:4:A ABC B