Во время своих путешествий по Средиземью Бильбо пришлось изучить много языков.
Но особенно трудным в изучении оказался древнеэльфийский язык Квенья.
Бильбо даже завёл пергамент, на который он бережно выписывал квенийские слова.
Но вот все путешествия закончились, и Бильбо решил составить Квеньянско-Адунийский
словарь для хоббитов. Он тщательно осмотрел свои записи. И каково же было его удивление,
когда обнаружилось, что некоторые из записей на пергаменте, возможно, встречаются несколько раз.
Дело в том, что иногда Бильбо мог запечатлеть то или иное слово на свой пергамент с несколькими ошибками,
делая не более двух ошибок в одном слове. Ошибки могут быть следующими: пропущена одна буква, вставлена
одна лишняя буква, вместо одной буквы написана другая. Таким образом, одно и то же слово
могло попасть в пергамент как в правильной версии, так и в одной или нескольких ошибочных.
Перед составлением словаря хотелось бы найти все такие слова. Помогите Бильбо в этом.
Нам также известно, что для любого слова правильный вариант его написания точно находится на
пергаменте Бильбо.
Исходные данные
В первой строке содержится целое число K — количество слов (1 ≤ K ≤ 5000).
В следующих K строках даны слова из пергамента Бильбо. Каждое слово — непустая строка,
содержащая не более 15 символов. Известно, что слова содержат только строчные английские буквы.
Все строки в списке различны.
Результат
Выведите все слова, которые (вместе с возможными вариантами их неправильного написания) встречаются
более одного раза. В первой строке необходимо вывести их количество. Далее по одному в строке выведите все эти слова
в лексикографическом порядке.
Пример
исходные данные | результат |
---|
7
lomba
pella
palpa
papa
moina
morna
sin | 5
moina
morna
palpa
papa
pella |
Автор задачи: Сергей Пупырев
Источник задачи: Восьмое открытое личное первенство УрГУ (3 марта 2007)