Запутанные Имена Пользователей
Университет Мейкёкан славится своими исследованиями и обучением в области компьютерных наук. В этом университете есть компьютерный центр, оснащенный передовыми и безопасными вычислительными ресурсами, включая суперкомпьютеры и множество персональных компьютеров, подключенных к Интернету.
Одна из политик компьютерного центра позволяет студентам выбирать свои собственные логины. Однако студенты часто выбирают похожие логины, что приводит к частым ошибкам при вводе или указании логинов. Эти ошибки создают значительные неудобства для сотрудников компьютерного центра.
Чтобы решить эту проблему, доктор Чоэй Такано, главный менеджер компьютерного центра, решил устранить похожие и вводящие в заблуждение логины. Для этого он должен разработать программу, которая будет выявлять такие логины.
Расстояние между двумя логинами определяется как минимальное количество операций, необходимых для преобразования одного логина в другой, с использованием следующих четырех операций:
Удаление символа в произвольной позиции.
Вставка символа в произвольную позицию.
Замена символа в произвольной позиции на другой символ.
Перестановка двух соседних символов в произвольной позиции.
Например, расстояние между "omura" и "murai" равно двум, так как следующая последовательность операций преобразует "omura" в "murai".
Другой пример: расстояние между "akasan" и "kaason" также равно двум.
Такано решил, что логины с небольшим расстоянием считаются вводящими в заблуждение и должны быть исключены.
Ваша задача — написать программу, которая перечисляет все вводящие в заблуждение пары логинов.
Обратите внимание, что правила могут сочетаться сложным образом. Например, расстояние между "ant" и "neat" равно двум.
Входные данные
Входные данные состоят из нескольких наборов. Каждый набор данных представлен в следующем формате.
n
d
name_1
name_2
...
name_n
Первое целое число n — это количество логинов. Затем идет положительное целое число d. Два логина считаются вводящими в заблуждение, если расстояние между ними меньше или равно d. Вы можете предположить, что 0 < n ≤ 200 и 0 < d ≤ 2. Логин i-го студента задается name[i], который состоит только из строчных букв и имеет длину менее 16. Вы можете предположить, что в name[i] нет дубликатов (1 ≤ i ≤ n).
Конец ввода обозначается строкой, содержащей только ноль.
Выходные данные
Для каждого набора данных ваша программа должна выводить все пары вводящих в заблуждение логинов, по одной паре на строку, а затем общее количество таких пар в наборе данных.
В каждой паре два логина должны быть разделены запятой (,), и логин, который алфавитно предшествует другому, должен быть первым. Все вводящие в заблуждение пары для каждого набора данных должны быть отсортированы следующим образом: для двух пар "w1, w2" и "w3, w4", если w1 алфавитно предшествует w3, или они одинаковы и w2 предшествует w4, то "w1, w2" должно появляться перед "w3, w4".