Пропозиція виправлення орфографії
Пропозиція виправлення орфографії є частиною програми корекції орфографії, яка генерує набір можливих замін для слів, що, ймовірно, містять помилки. Один із способів оцінити ймовірність цих замін — це обчислити їхню відстань редагування відносно заданого слова з помилкою. Відстань редагування між двома словами — це загальна кількість операцій редагування, необхідних для перетворення одного слова в інше. Зазвичай ці операції включають вставку, видалення та заміну одного символу, а також транспозицію 2 послідовних символів.
Наприклад, для слова "wonder", якщо видалити символ 'o', воно перетвориться на "wnder". Якщо замінити 'o' на 'a', воно стане "wander". А якщо застосувати транспозицію до "er", воно стане "wondre".
У цій стратегії відстань редагування визначає ступінь схожості між двома словами через їхню мінімальну відстань редагування. Якщо мінімальна відстань редагування між word_1 і word_2 менша, ніж між word_1 і word_3, то word_1 більше схоже на word_2, ніж на word_3. Отже, word_2 є кращою пропозицією виправлення для word_1 у порівнянні з word_3.
Припустимо, що ви працюєте в програмній компанії, яка повинна створити прототип програми для пропозицій виправлення орфографії. Цей прототип має бути частиною програмного забезпечення для обробки текстів. Вимога полягає в тому, що він повинен використовувати стратегію відстані редагування для своїх пропозицій виправлення. Однак операція заміни повинна бути адаптована, щоб відповідати поведінці помилкового набору. Вартість заміни одного символу на інший залежить від їхнього розташування на клавіатурі. Якщо вони близькі один до одного, вартість становить лише половину від звичайної. Для цього заміна поділяється на близьку заміну та далеку заміну. Їхні вартості визначені як 1 і 2 відповідно. А вартість вставки, видалення та транспозиції становить 2. Крім того, ця програма повинна працювати досить швидко, щоб пройти обмеження часу, встановлене вашим менеджером. До речі, для цього прототипу обрано англійську клавіатуру QWERTY.
Мета
Згенерувати оптимальні пропозиції виправлення орфографії для кожного вхідного слова, де кожна оптимальна пропозиція виправлення — це слово в словнику, яке має найменшу мінімальну відстань редагування від заданого вхідного слова. Обмеження часу для 5,000 слів з помилками становить менше або дорівнює 5 хвилинам.
Вхідні дані
Вхід — це стандартний вхід, який містить 3 частини даних. Кожна з цих трьох частин закінчується порожнім рядком.
Перша частина — це набір правил близької заміни, де кожне правило зберігається в одному рядку. Кожен рядок має два поля, розділені пробілом. Загальна кількість правил не перевищує 150.
Перше поле — це символ, який може бути близько замінений іншими символами.
Друге поле — це послідовність символів, які можуть бути близько замінені на символ у попередньому полі. У цьому полі немає пробілів.
Символи, які можуть бути в цій частині, — це символи, які можна набрати за допомогою стандартної англійської клавіатури, які є алфавітно-цифровими символами та деякими пунктуаціями без пробілів або табуляцій. Вони перераховані наступним чином.
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789' !@#$%^*()-_=+|[{]};:'”,<.>/?
Друга частина — це послідовність слів у словнику, де кожне слово зберігається в одному рядку. Загальна кількість слів не перевищує 150,000.
Символи в словнику — це алфавітні символи з апострофом.
abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ’
Третя частина — це послідовність слів, які потрібно перевірити на орфографію. Кожне з цих слів також зберігається в одному рядку. Загальна кількість слів не перевищує 5,000.
Символи, які можуть бути в цій частині, такі ж, як і символи в першій частині, які є алфавітно-цифровими символами та деякими пунктуаціями. (Див. першу частину.)
Оскільки кожна з цих трьох частин закінчується порожнім рядком, третій порожній рядок є завершенням вводу.
Вихідні дані
Для кожного слова в третій частині напишіть рядок, який містить 3 частини інформації, розділені двокрапкою.
Перша частина — це задане вхідне слово.
Друга частина — це мінімальна відстань редагування між вхідним словом і словом-пропозицією.
Третя частина — це відсортована за зростанням послідовність слів-пропозицій, розділених пробілом. Після останнього слова не залишено пробілів.
Додаткові пояснення
У цьому прикладі вводу є 5 правил близької заміни (рядки № 1-5), 10 слів у словнику (рядки № 7-16) і 12 слів, які шукають свої пропозиції (рядки № 18-29).
У прикладі виводу є 12 рядків для кожного з 12 слів з вводу.
Для 1-го слова мінімальна відстань редагування між x і його пропозиціями (A B Z a b) становить 2.
Усі вони є вартістю (далекої) заміни.
Для 2-го слова мінімальна відстань редагування між s і його пропозицією (a) становить 1, що є вартістю близької заміни, згідно з 1-м правилом заміни.
Для 3-го слова мінімальна відстань редагування між z і його пропозицією (A Z a) становить 1, що є вартістю близької заміни, згідно з 1-м або 5-м правилом заміни.
Для 4-го слова мінімальна відстань редагування становить 4, що складається з однієї вартості далекої заміни та однієї вартості видалення.
Для 5-го слова мінімальна відстань редагування становить 6. Вартість між xxx і (A B Z a b) складається з двох вартостей видалення та однієї вартості далекої заміни. Вартість між xxx і ABC складається з трьох вартостей далекої заміни.
Для 6-го слова вартість між angre і anger складається з однієї вартості транспозиції. Вартість між angre і (angle angry) складається з однієї вартості далекої заміни.
Для 7-го та 8-го слова, здається, вони схожі. Але вартість 7-го слова складається з однієї вартості далекої заміни. Але вартість між angrt і anger складається з 2 вартостей близької заміни (r замінюється на e і t замінюється на r) згідно з правилом близької заміни № 4.
Для 9-го слова слово точно збігається зі словником. Отже, вартість становить 0.
Для 10-го та 11-го слова кожна вартість складається з однієї вартості транспозиції.
Для 12-го слова вартість між CAB і (A B) складається з двох вартостей видалення. Вартість між CAB і (ABC) складається з однієї вартості видалення та однієї вартості вставки. Зверніть увагу, що це не від 2 транспозицій CAB до ACB, а потім ACB до ABC.